Tight bounds for online coloring of basic graph classes
DOI10.4230/LIPICS.ESA.2017.7zbMATH Open1442.68159OpenAlexW2964175068MaRDI QIDQ5111690FDOQ5111690
Authors: 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/
Recommendations
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
- On the power of randomization in on-line algorithms
- Title not available (Why is that?)
- Online coloring of bipartite graphs with and without advice
- Title not available (Why is that?)
- 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: from offline to online
- 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
- An improved competitive algorithm for reordering buffer management
- A tight bound for online colouring of disk graphs
- Online conflict-free colouring for hypergraphs
- Online graph coloring with advice and randomized adversary (extended abstract)
- 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 (14)
- A tight bound for online colouring of disk graphs
- Title not available (Why is that?)
- Online Bounded Coloring of Permutation and Overlap Graphs
- A refined analysis of online path coloring in trees
- Batch coloring of graphs
- Online chromatic number is PSPACE-complete
- Online graph coloring against a randomized adversary
- The power of amortized recourse for online graph problems
- Coloring inductive graphs on-line
- Max-coloring and online coloring with bandwidths on interval graphs
- Tight bounds for online coloring of basic graph classes
- Structural Information and Communication Complexity
- Title not available (Why is that?)
- 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)
