G =(V,E), a specified set of vertices Γ
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E88-A No.5 pp.1290-1300
Publication Date: 2005/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
graphs, augmentation problems, edge-connectivity, approximation algorithms,
Full Text: PDF(389.2KB)
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 ′.