Tight bounds for online coloring of basic graph classes
DOI10.1007/S00453-020-00759-7OpenAlexW3080569475MaRDI QIDQ2223701FDOQ2223701
Authors: Susanne Albers, Sebastian Schraink 
Publication date: 1 February 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1702.07172
Recommendations
Online algorithms; streaming algorithms (68W27) 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
- 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
- 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)
- Online graph coloring against a 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
- A Constant Factor Approximation Algorithm for Reordering Buffer Management
- Batch coloring of graphs
- An improved competitive algorithm for reordering buffer management
Cited In (17)
- A tight bound for online colouring of disk graphs
- Online coloring known 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 dominating set and coloring
- Coloring inductive graphs on-line
- Max-coloring and online coloring with bandwidths on interval graphs
- Online coloring of short intervals
- Tight bounds for online coloring of basic graph classes
- Structural Information and Communication Complexity
- Bounded families for the on-line \(t\)-relaxed coloring
- Parameterized and Exact Computation
- 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 Q2223701)
