Fast algorithms for edge-coloring planar graphs

DOI10.1016/0196-6774(89)90022-9MaRDI QIDQ3815319zbMATH OpenOpenAlexFDO

Authors Marek Chrobak, Moti Yung

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0196-6774(89)90022-9

zbMATH Keywords

algorithmsedge-coloringoptimal coloringplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 4076639
• Improved edge-coloring algorithms for planar graphs
• An efficient algorithm for edge coloring planar graphs with \(\Delta\) colors
• New linear-time algorithms for edge-coloring planar graphs
• Coloring planar graphs in parallel

Cited in

(21)

• Heuristic for rapidly four-coloring large planar graphs
• New linear-time algorithms for edge-coloring planar graphs
• scientific article; zbMATH DE number 432820 (Why is no real title available?)
• Improved edge-coloring algorithms for planar graphs
• Coloring planar graphs in parallel
• scientific article; zbMATH DE number 4047151 (Why is no real title available?)
• scientific article; zbMATH DE number 4076639 (Why is no real title available?)
• Optimal Parallel 5-Colouring of Planar Graphs
• REGION COLORING, EDGE COLORING, AND SCAN-CONVERSION OF MAPS
• Efficient algorithms for the edge-cover coloring problem
• Tight lower bounds for list edge coloring
• Fast edge colorings with fixed number of colors to minimize imbalance
• Fast Edge Colorings with Fixed Number of Colors to Minimize Imbalance
• Faster graph coloring in polynomial space
• The maximal f-dependent set problem for planar graphs is in NC
• The maximal \(f\)-dependent set problem for planar graphs is in NC
• Fast algorithms for Vizing's theorem on bounded degree graphs
• Edge-coloring sparse graphs with Colors in quasilinear time
• Vizing's theorem in near-linear time
• An efficient algorithm for edge coloring planar graphs with \(\Delta\) colors
• Graph coloring in linear time

This page was built for publication: Fast algorithms for edge-coloring planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3815319)