Algorithms for finding distance-edge-colorings of graphs

DOI10.1016/j.jda.2006.03.020zbMath1125.05099OpenAlexW2144580685MaRDI QIDQ2457301

Takao Nishizeki, Xiao Zhou, Takehiro Ito, Akira Kato

Publication date: 30 October 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.03.020

zbMATH Keywords

approximation algorithmplanar graphspartial \(k\)-treesdistance-edge-coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Distance edge coloring and collision‐free communication in wireless sensor networks ⋮ Local algorithms for edge colorings in UDGs ⋮ On the complexity of the flow coloring problem ⋮ Distance edge-colourings and matchings ⋮ On distance edge-colourings and matchings

Cites Work

• Unnamed Item
• Monadic second-order evaluations on tree-decomposable graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• A partial k-arboretum of graphs with bounded treewidth
• On the computational complexity of strong edge coloring
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
• 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
• Short path queries in planar graphs in constant time
• Edge-Coloring Partialk-Trees
• The NP-Completeness of Edge-Coloring
• An algebraic theory of graph reduction
• Approximation algorithms for NP-complete problems on planar graphs
• Coloring Powers of Planar Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Computing and Combinatorics