The greedy algorithm is optimal for on-line edge coloring

DOI10.1016/0020-0190(92)90209-EzbMath0768.68117WikidataQ56390611 ScholiaQ56390611MaRDI QIDQ1209350

Amotz Bar-Noy, Joseph (Seffi) Naor

Publication date: 16 May 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

graph coloringrandomized algorithmon-line edge coloringoptimal greedy algorithm

Mathematics Subject Classification ID

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

Related Items (14)

On-line algorithms for the dominating set problem ⋮ Online Dual Edge Coloring of Paths and Trees ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ A new vertex coloring heuristic and corresponding chromatic number ⋮ Maximal edge-colorings of graphs ⋮ Maximal edge colorings of graphs ⋮ Online Edge Coloring via Tree Recurrences and Correlation Decay ⋮ Graph coloring with rejection ⋮ Online edge coloring of paths and trees with a fixed number of colors ⋮ Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting) ⋮ Inequalities for the Grundy chromatic number of graphs ⋮ Analysis of approximate algorithms for edge-coloring bipartite graphs ⋮ Comparing first-fit and next-fit for online edge coloring ⋮ Bounded families for the on-line \(t\)-relaxed coloring

Cites Work

• Unnamed Item
• An on-line graph coloring algorithm with sublinear performance ratio
• Improving the performance guarantee for approximate graph coloring
• On-line and first fit colorings of graphs
• The Linearity of First-Fit Coloring of Interval Graphs

This page was built for publication: The greedy algorithm is optimal for on-line edge coloring