Optimal Parallel Algorithms for Edge-Coloring Partial k-Trees with Bounded Degrees
スポンサーリンク
概要
- 論文の詳細を見る
Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by k). The edge-coloring problem is one of the well-known combinatorial problems for which no NC algorithms have been obtained for partial k-trees. This paper gives an optimal and first NC parallel algorithm to find an edge-coloring of any given partial k-tree with bounded degrees using a minimum number of colors. In the paper k is assumed to be bounded.
- 社団法人電子情報通信学会の論文
- 1995-04-25
著者
-
Nishizeki Takao
Department Of Electrical Communications Faculty Of Engineering Tohoku University
-
Zhou X
Tohoku Univ. Sendai‐shi Jpn
-
Zhou Xiao
Tohoku Univ. Sendai‐shi Jpn
-
Zhou Xiao
Department Of Pathology Jinling Hospital
-
Nishizeki Takao
Department Of System Information Sciences Graduate School Of Information Sciences Tohoku University
関連論文
- List Edge-Colorings of Series-Parallel Graphs
- Linear Algorithm for Finding List Edge-Colorings of Series-Parallel Graphs (Special Issue on Selected Papers from LA Symposium)
- Examination of the Mechanism of Oleic Acid-Induced Percutaneous Penetration Enhancement : an Ultrastructural Study(Biopharmacy)
- Topical dorsal skin immersion in seawater induces apoptosis and proliferation in hairless mice
- 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)
- Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size(Graph Algorithms,Foundations of Computer Science)
- Algorithms for Multicolorings of Partial ★-Trees (Special Issue on Selected Papers from LA Symposium)
- Optimal Parallel Algorithms for Edge-Coloring Partial k-Trees with Bounded Degrees
- Editors' Introduction to Special Section on Discrete Algorithms and Complexity
- Graph Coloring Algorithms(Special Issue on Algorithm Engineering : Surveys)
- NP-Completeness of the Hamiltonian Cycle Problem for Bipartite Graphs
- Biophysical and morphological changes in the stratum corneum lipids induced by UVB irradiation
- Morphological alterations of the stratum corneum lipids induced by sodium lauryl sulfate treatment in hairless mice