Algorithms for finding distance-edge-colorings of graphs
From MaRDI portal
Publication:2457301
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
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 (5)
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
This page was built for publication: Algorithms for finding distance-edge-colorings of graphs
