The greedy algorithm is optimal for on-line edge coloring
From MaRDI portal
Publication:1209350
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)
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
This page was built for publication: The greedy algorithm is optimal for on-line edge coloring