Paper Abstract and Keywords |
Presentation |
2004-09-17 15:30
Minimum 2-Vertex-Connectivity Augmentation for Specified Vertices of a Graph with Degree Constraints Toshiya Mashima (Hiroshima International Univ.), Takanori Fukuoka, Satoshi Taoka, Toshimasa Watanabe (Hiroshima Univ.) |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
The 2-vertex-connectivity augmentation problem for a specified set ofvertices of a graph with degree constraints, 2VCA-SV-DC, is defined as follows: ``Given an undirected graph $G=(V,E)$, a specified set of vertices $S_0\subseteq V$ with $|S_0|\geq 3$ and a function $g: V\to Z^+\cup\{\infty\}$, find a smallest set $E'$ of edges such that $(V,E\cup E')$ has at least two internally-disjoint paths between any pair of vertices in $S_0$ and such that vertex-degree increase of each $v\in V$ by the addition of $E'$ to $G$ is at most $g(v)$, where $Z^+$ is the set of nonnegative integers.''This paper shows a linear time algorithm for 2VCA-SV-DC. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
graphs / vertex-connectivity of a specified set of vertices / augmentation problems / degree constraints / linear time algorithms / / / |
Reference Info. |
IEICE Tech. Rep., vol. 104, no. 317, COMP2004-33, pp. 57-64, Sept. 2004. |
Paper # |
COMP2004-33 |
Date of Issue |
2004-09-10 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
Download PDF |
|
|