Tight Bounds for Online Coloring of Basic Graph Classes
DOI10.4230/LIPICS.ESA.2017.7zbMATH Open1442.68159OpenAlexW2964175068MaRDI QIDQ5111690FDOQ5111690
Susanne Albers, Sebastian Schraink
Publication date: 27 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7826/pdf/LIPIcs-ESA-2017-7.pdf/
Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the power of randomization in on-line algorithms
- Online coloring of bipartite graphs with and without advice
- Characterizations of strongly chordal graphs
- Parallel and On-Line Graph Coloring
- Effective coloration
- On-line coloring \(k\)-colorable graphs
- Coloring inductive graphs on-line
- On-line and first fit colorings of graphs
- Deterministic conflict-free coloring for intervals
- An on-line graph coloring algorithm with sublinear performance ratio
- Randomized online graph coloring
- Lower bounds for on-line graph coloring
- The Power of Reordering for Online Minimum Makespan Scheduling
- A tight bound for online colouring of disk graphs
- Online Conflict-Free Colouring for Hypergraphs
- Online Graph Coloring with Advice and Randomized Adversary
- Independence and Coloring Problems on Intersection Graphs of Disks
- On-line coloring of geometric intersection graphs
- Online promise problems with online width metrics
Cited In (9)
- A tight bound for online colouring of disk graphs
- Title not available (Why is that?)
- Online Bounded Coloring of Permutation and Overlap Graphs
- Batch coloring of graphs
- Online chromatic number is PSPACE-complete
- The power of amortized recourse for online graph problems
- Max-coloring and online coloring with bandwidths on interval graphs
- Structural Information and Communication Complexity
- Online coloring and a new type of adversary for online graph problems
This page was built for publication: Tight Bounds for Online Coloring of Basic Graph Classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111690)
