Graph Augmentation Problems with Degree-Unchangeable Vertices(Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)

スポンサーリンク

概要

• 論文の詳細を見る

• The κ-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree-unchangeable vertices, κVCA(G, S, D), is defined as follows: "Given a positive integer κ, an undirected graph G=(V, E), a specified set of vertices S⊆V and a set of degree-changeable vertices D⊆V, find a smallest set of edges E′ such that the vertex-connectivity of S in(v, e∪E′)is at least κ and E′⊆{(u, υ)|u, υ∈D}." The main result of the paper is that checking the existence of a solution and finding a solution to 2VCA(G, S, D)or 3VCA(G, S, D)can be done in O(|V|+|E|)or O(|V|(|V|+|E|))time, respectively.

• 社団法人電子情報通信学会の論文
• 2001-03-01

著者

• Watanabe Toshimasa

  Department Of Circuits And Systems Faculty Of Engineering Hiroshima University

• MASHIMA Toshiya

  Department of Computer Engineering, Faculty of Information Sciences, Hiroshima City University

• Mashima Toshiya

  Department Of Computer Engineering Faculty Of Information Sciences Hiroshima City University

関連論文

• Time Complexity Analysis of the Minimal Siphon Extraction Problem of Petri Nets (Special Section on Concurrent Systems Technology)
• Graph Augmentation Problems with Degree-Unchangeable Vertices(Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
• A Heuristic Algorithm FMDB for the Minimum Initial Marking Problem of Petri Nets(Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
• Algorithms for Extracting Minimal Siphons Containing Specified Places in a General Petri Net (Special Section on Concurrent Systems Technology)
• On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
• A 2-Approximation Algorithm to (k+1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph(Discrete Mathematics and Its Applications)
• A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase(Selected Papers from the 17th Workshop on Circuits and Systems in Karuizawa)
• A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints

スポンサーリンク