A 2-Approximation Algorithm to (<I>k</I> + 1)-Edge-Connect a Specified Set of Vertices in a <I>k</I>-Edge-Connected Graph

Toshiya MASHIMA; Satoshi TAOKA; Toshimasa WATANABE

doi:10.1093/ietfec/e88-a.5.1290

A 2-Approximation Algorithm to (k + 1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph

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 ((k + δ)ECA-SV) is defined as follows: "Given an undirected graph G =(V,E), a specified set of vertices Γ V, a subgraph G ′=(V,E ′) with λ(Γ;G ′) = k of G and a cost function c: E Z⁺ (nonnegative integers), find a set E^* E - E ′of edges, each connecting distinct vertices of V, of minimum total cost such that λ(Γ;G″) k + δ for G"=(V,E ′∪E^*)," where λ(Γ;G″) is the minimum value of the maximum number of edge disjoint paths between any pair of vertices in Γ of G". The paper proposes an O(Δ+|V||E|) time 2-approximation algorithm FSAR for (k + 1)ECA-SV with a restriction λ(V;G ′) = λ(Γ;G ′), where Δ is the time complexity of constructing a structural graph of a given graph G ′.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.5 pp.1290-1300

Publication Date: 2005/05/01

Publicized

Online ISSN

DOI: 10.1093/ietfec/e88-a.5.1290

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Toshiya MASHIMA, Satoshi TAOKA, Toshimasa WATANABE, "A 2-Approximation Algorithm to (k + 1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph" in IEICE TRANSACTIONS on Fundamentals, vol. E88-A, no. 5, pp. 1290-1300, May 2005, doi: 10.1093/ietfec/e88-a.5.1290.
Abstract: The (k + δ)-edge-connectivity augmentation problem for a specified set of vertices ((k + δ)ECA-SV) is defined as follows: "Given an undirected graph G =(V,E), a specified set of vertices Γ V, a subgraph G ′=(V,E ′) with λ(Γ;G ′) = k of G and a cost function c: E Z⁺ (nonnegative integers), find a set E^* E - E ′of edges, each connecting distinct vertices of V, of minimum total cost such that λ(Γ;G″) k + δ for G"=(V,E ′∪E^*)," where λ(Γ;G″) is the minimum value of the maximum number of edge disjoint paths between any pair of vertices in Γ of G". The paper proposes an O(Δ+|V||E|) time 2-approximation algorithm FSAR for (k + 1)ECA-SV with a restriction λ(V;G ′) = λ(Γ;G ′), where Δ is the time complexity of constructing a structural graph of a given graph G ′.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.5.1290/_p

Copy

@ARTICLE{e88-a_5_1290,
author={Toshiya MASHIMA, Satoshi TAOKA, Toshimasa WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A 2-Approximation Algorithm to (k + 1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph},
year={2005},
volume={E88-A},
number={5},
pages={1290-1300},
abstract={The (k + δ)-edge-connectivity augmentation problem for a specified set of vertices ((k + δ)ECA-SV) is defined as follows: "Given an undirected graph G =(V,E), a specified set of vertices Γ V, a subgraph G ′=(V,E ′) with λ(Γ;G ′) = k of G and a cost function c: E Z⁺ (nonnegative integers), find a set E^* E - E ′of edges, each connecting distinct vertices of V, of minimum total cost such that λ(Γ;G″) k + δ for G"=(V,E ′∪E^*)," where λ(Γ;G″) is the minimum value of the maximum number of edge disjoint paths between any pair of vertices in Γ of G". The paper proposes an O(Δ+|V||E|) time 2-approximation algorithm FSAR for (k + 1)ECA-SV with a restriction λ(V;G ′) = λ(Γ;G ′), where Δ is the time complexity of constructing a structural graph of a given graph G ′.},
keywords={},
doi={10.1093/ietfec/e88-a.5.1290},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - A 2-Approximation Algorithm to (k + 1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1290
EP - 1300
AU - Toshiya MASHIMA
AU - Satoshi TAOKA
AU - Toshimasa WATANABE
PY - 2005
DO - 10.1093/ietfec/e88-a.5.1290
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2005
AB - The (k + δ)-edge-connectivity augmentation problem for a specified set of vertices ((k + δ)ECA-SV) is defined as follows: "Given an undirected graph G =(V,E), a specified set of vertices Γ V, a subgraph G ′=(V,E ′) with λ(Γ;G ′) = k of G and a cost function c: E Z⁺ (nonnegative integers), find a set E^* E - E ′of edges, each connecting distinct vertices of V, of minimum total cost such that λ(Γ;G″) k + δ for G"=(V,E ′∪E^*)," where λ(Γ;G″) is the minimum value of the maximum number of edge disjoint paths between any pair of vertices in Γ of G". The paper proposes an O(Δ+|V||E|) time 2-approximation algorithm FSAR for (k + 1)ECA-SV with a restriction λ(V;G ′) = λ(Γ;G ′), where Δ is the time complexity of constructing a structural graph of a given graph G ′.
ER -