Online coloring and a new type of adversary for online graph problems

DOI10.1007/978-3-030-80879-2_4OpenAlexW3186619231MaRDI QIDQ5918632

Yaqiao Li, Vishnu V. Narayan, Denis Pankratov

Publication date: 22 March 2022

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2005.10852

zbMATH Keywords

connected componentsonline algorithmsonline coloringfirst fitCBIPparameterized analysis

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Online coloring of bipartite graphs with and without advice
• An on-line graph coloring algorithm with sublinear performance ratio
• On-line coloring \(k\)-colorable graphs
• A partial k-arboretum of graphs with bounded treewidth
• Lower Bounds for On-line Graph Colorings
• Emergence of Scaling in Random Networks
• On-line and first fit colorings of graphs
• Effective coloration
• Tight Bounds for Online Coloring of Basic Graph Classes
• Networks

This page was built for publication: Online coloring and a new type of adversary for online graph problems