A parallel algorithm for edge-coloring partial k-trees

DOI10.1007/3-540-58218-5_33zbMath1502.68248OpenAlexW1553907219MaRDI QIDQ5054775

Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58218-5_33

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Planar graphs: Theory and algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• Improved edge-coloring algorithms for planar graphs
• A generalization of edge-coloring in graphs
• On the f-coloring of multigraphs
• Efficient parallel algorithms for edge coloring problems
• The NP-Completeness of Edge-Coloring
• Linear-time computability of combinatorial problems on series-parallel graphs
• An algebraic theory of graph reduction
• A linear time algorithm for finding tree-decompositions of small treewidth

This page was built for publication: A parallel algorithm for edge-coloring partial k-trees