Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree Increase(Graph Algorithm, <Special Section> Foundations of Computer Science)
スポンサーリンク
概要
- 論文の詳細を見る
The 2-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, 2VCA-SV-DC, is defined as follows: "Given an undirected graph G=(V, E), a specified set of vertices S⊆V with |S|≥3 and a function g: V→Z^+∪{∞}, 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 S and such that vertex-degree increase of each v∈V by the addition of E' to G is at most g(v), where Z^+ is the set of nonnegative integers." This paper shows a linear time algorithm for 2VCA-SV-DC.
- 社団法人電子情報通信学会の論文
- 2006-02-01
著者
-
Taoka Satoshi
Hiroshima Univ. Higashihiroshima‐shi Jpn
-
TAOKA Satoshi
the Graduate School of Engineering, Hiroshima University
-
WATANABE Toshimasa
the Graduate School of Engineering, Hiroshima University
-
Watanabe Toshimasa
Hiroshima Univ. Higashi‐hiroshima Jpn
-
MASHIMA Toshiya
the Department of Information Technology, Faculty of Infrastructural Technologies, Hiroshima Interna
-
FUKUOKA Takanori
the Graduate School of Engineering, Hiroshima University
-
Fukuoka Takanori
The Graduate School Of Engineering Hiroshima University
-
Mashima Toshiya
Department Of Information And Communications Technology Faculty Of Engineering Hiroshima International University
関連論文
- Two Enhanced Heuristic Algorithms for the Minimum Initial Marking Problem of Petri Nets
- Improved Heuristic Algorithms for Minimizing Initial Markings of Petri Nets(Concurrent/Hybrid Systems : Theory and Applications)
- Experimental Evaluation of Two Algorithms for Computing Petri Net Invariants(Special Section on Concurrent Systems Technology)
- Enhancing PC Cluster-Based Parallel Branch-and-Bound Algorithms for the Graph Coloring Problem
- Enhanced Approximation Algorithms for Maximum Weight Matchings of Graphs
- Performance Comparison of Algorithms for the Dynamic Shortest Path Problem(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
- Performance comparison of algorithms for the dynamic shortest path problem (グラフアルゴリスム)
- Finding Minimal Siphons in General Petri Nets (Special Section on Description Models for Concurrent Systems and Their Applications)
- A linear time algorithm for tri-connectivity augmentation of bi-connected graphs with upper bounds on vertex-degree increase (第21回 回路とシステム軽井沢ワークショップ論文集) -- (グラフアルゴリズム)
- 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)
- Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree Increase(Graph Algorithm, Foundations of Computer Science)
- 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)
- Extracting Minimal Siphon-Traps of Petri Nets and Its Application to Computing Nonnegative Integer-Invariants(Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- Tri-connectivity augmentation problems for bi-connected graphs with upper bounds on vertex-degree increase (ネツトワークの信頼性)
- FOREWORD
- A Fast Algorithm for Augmenting Edge-Connectivity by One with Bipartition Constraints
- Two Heuristic Algorithms for the Minimum Initial Marking Problem of Timed Petri Nets