On Minimum <I>k</I>-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree

Toshiya MASHIMA; Satoshi TAOKA; Toshimasa WATANABE

doi:10.1093/ietfec/e89-a.4.1042

On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree

Toshiya MASHIMA, Satoshi TAOKA, Toshimasa WATANABE

Full Text Views

0

Cite this

Summary :

The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z⁺ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z⁺ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.4 pp.1042-1048

Publication Date: 2006/04/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.4.1042

Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)

Category

Cite this

Copy

Toshiya MASHIMA, Satoshi TAOKA, Toshimasa WATANABE, "On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 4, pp. 1042-1048, April 2006, doi: 10.1093/ietfec/e89-a.4.1042.
Abstract: The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z⁺ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z⁺ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.4.1042/_p

Copy

@ARTICLE{e89-a_4_1042,
author={Toshiya MASHIMA, Satoshi TAOKA, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree},
year={2006},
volume={E89-A},
number={4},
pages={1042-1048},
abstract={The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z⁺ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z⁺ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.},
keywords={},
doi={10.1093/ietfec/e89-a.4.1042},
ISSN={1745-1337},
month={April},}

Copy

TY - JOUR
TI - On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1042
EP - 1048
AU - Toshiya MASHIMA
AU - Satoshi TAOKA
AU - Toshimasa WATANABE
PY - 2006
DO - 10.1093/ietfec/e89-a.4.1042
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2006
AB - The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z⁺ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z⁺ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.
ER -