Applications of the Lipton and Tarjan's Planar Separator Theorem
スポンサーリンク
概要
- 論文の詳細を見る
Using the planar separator theorem of Lipton and Tarjan, we give approximation algorithms with time complexity O(n log n) and asymptotic worst-case ratio tending to 1 for the following problems on planar graphs: the maximum induced subgraph problems with respect to certain graph propertles; the maximum matching problem; and the minimum vertex over problem.
- 一般社団法人情報処理学会の論文
- 1982-02-25
著者
-
Nishizeki Takao
Department Of Electrical Communications Faculty Of Engineering Tohoku University
-
CHIBA NORISHIGE
Department of Electrical Communications, Faculty of Engineering, Tohoku University
-
SAITO NOBUJI
Department of Electrical Communications, Faculty of Engineering, Tohoku University
-
Saito Nobuji
Department Of Electrical Communications Faculty Of Engineering Tohoku University
-
Chiba Norishige
Department Of Electrical Communications Faculty Of Engineering Tohoku University
-
Chiba Norishige
Department Of Computer And Information Sciences Graduate School Of Engineering Iwate University
関連論文
- Applications of the Lipton and Tarjan's Planar Separator Theorem
- Applications of the Lipton and Tarjan's Planar Separator Theorem (Applied Combinatorial Theory and Algorithms)
- Optimal Parallel Algorithms for Edge-Coloring Partial k-Trees with Bounded Degrees
- Editors' Introduction to Special Section on Discrete Algorithms and Complexity
- NP-Completeness of the Hamiltonian Cycle Problem for Bipartite Graphs
- MULTI-PURPOSE RECURSIVE MAPPING METHOD FOR ANIMATING LARGE-SCALE CUMULONIMBUS CLOUDS(INTERNATIONAL Workshop on Advanced Image Technology 2008)
- MORPHING-BASED VECTORIZED CANDLE ANIMATION FOR LASER GRAPHICS(International Workshop on Advanced Image Technology 2007)
- MORPHING-BASED VECTORIZED CANDLE ANIMATION FOR LASER GRAPHICS
- VECTOR-BASED LIBRARY FOR DISPLAYING BEZIER CURVES USING A LASER PROJECTOR(International Workshop on Advanced Image Technology 2007)
- VECTOR-BASED LIBRARY FOR DISPLAYING BEZIER CURVES USING A LASER PROJECTOR
- VOLUMETRIC PARTICLE METHOD FOR ANIMATING VISCOUS FLUIDS(International Workshop on Advanced Image Technology 2006)
- NOISE-BASED ANIMATION OF WAVING PHENOMENA(International Workshop on Advanced Image Technology 2005)