
For FullText 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 2Approximation Algorithm to (k + 1)EdgeConnect a Specified Set of Vertices in a kEdgeConnected Graph
Toshiya MASHIMA Satoshi TAOKA Toshimasa WATANABE
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E88A
No.5
pp.12901300 Publication Date: 2005/05/01
Online ISSN: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: graphs, augmentation problems, edgeconnectivity, approximation algorithms,
Full Text: PDF(389.2KB) >>Buy this Article
Summary:
The (k + δ)edgeconnectivity augmentation problem for a specified set of vertices ((k + δ)ECASV) 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(Δ+VE) time 2approximation algorithm FSAR for (k + 1)ECASV with a restriction λ(V;G ′) = λ(Γ;G ′), where Δ is the time complexity of constructing a structural graph of a given graph G ′.

