Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs
スポンサーリンク
概要
- 論文の詳細を見る
In this paper we propose an algorithm for generating maximum weight independent sets in a circle graph, that is, for putting out all maximum weight independent sets one by one without duplication. The time complexity is O(n^3+β), where n is the number of vertices, β output size, i.e., the sum of the cardinalities of the output sets. It is shown that the same approach can be applied for spider graphs and for circular-arc overlap graphs.
- 社団法人電子情報通信学会の論文
- 1999-08-25
著者
-
Kashiwabara Toshinobu
Department Of Bioinformatic Engineering Guraduate School Of Information Science And Technology Osaka
-
Kashiwabara Toshinobu
Department Of Information And Computer Sciences Osaka University
-
TAKI Masakuni
Department of Information Engineering, Nara National College of Technology
-
HATAKENAKA Hirotaka
Department of Information and Computer Sciences, Osaka University
-
Taki Masakuni
Department Of Information Engineering Nara National College Of Technology
-
Hatakenaka Hirotaka
Department Of Information And Computer Sciences Osaka University
関連論文
- Verifying Signal-Transition Consistency of High-Level Designs Based on Symbolic Simulation(Special Issue on Test and Verification of VLSI)
- A Partially Explicit Method for Efficient Symbolic Checking of Language Containment (Special Section on VLSI Design and CAD Algorithms)
- Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs
- On the Power of Non-deterministic Quantum Finite Automata(Special Issue on Selected Papers from LA Symposium)
- An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division (Special Section on Discrete Mathematics and Its Applications)