A 2-Approximation Algorithm to (k+1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph(<Special Section>Discrete Mathematics and Its Applications)

概要

論文の詳細を見る
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′.
社団法人電子情報通信学会の論文
2005-05-01