Comparing first-fit and next-fit for online edge coloring

DOI10.1016/j.tcs.2010.01.015zbMath1191.68881OpenAlexW2093548869MaRDI QIDQ964390

Rodica Mihai, Martin R. Ehmsen, Jens S. Kohrt, Lene Monrad Favrholdt

Publication date: 15 April 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.01.015

zbMATH Keywords

online algorithmscompetitive ratioedge coloringfirst-fitrelative worst-order rationext-fit

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items

Online Dual Edge Coloring of Paths and Trees ⋮ Online edge coloring of paths and trees with a fixed number of colors

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The relative worst-order ratio applied to paging
• Competitive snoopy caching
• Explicit constructions of linear-sized superconcentrators
• The greedy algorithm is optimal for on-line edge coloring
• A new measure for the study of on-line algorithms
• On-line edge-coloring with a fixed number of colors
• Separating online scheduling algorithms with the relative worst order ratio
• The relative worst order ratio for online algorithms
• Algorithm Theory - SWAT 2004
• Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem