A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase(<Special Section>Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)

概要

論文の詳細を見る
The 2-vertex-connectivity augmentation problem of a graph with degree constraints, 2VCA-DC, is defined as follows : "Given an undirected graph G=(V, E) and an upper bound a(υ;G)∈Z^+∪{∞} on vertex-degree increase for each υ∈V, find a smallest set E' of edges such that (V, E∪E') has at least two internally-disjoint paths between any pair of vertices in V and such that vertex-degree increase of each υ∈V by the addition of E' to G is at most a(υ;G), where Z^+ is the set of nonnegative integers." In this paper we show that checking the existence of a feasible solution and finding an optimum solution to 2VCA-DC can be done in O(|V|+|E|) time.
社団法人電子情報通信学会の論文
2005-04-01