Tight bounds for online coloring of basic graph classes
From MaRDI portal
Publication:5111690
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 3769624 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- A tight bound for online colouring of disk graphs
- An improved competitive algorithm for reordering buffer management
- An on-line graph coloring algorithm with sublinear performance ratio
- Characterizations of strongly chordal graphs
- Coloring inductive graphs on-line
- Deterministic conflict-free coloring for intervals: from offline to online
- Effective coloration
- Independence and Coloring Problems on Intersection Graphs of Disks
- Lower bounds for on-line graph coloring
- On the power of randomization in on-line algorithms
- On-line and first fit colorings of graphs
- On-line coloring \(k\)-colorable graphs
- On-line coloring of geometric intersection graphs
- Online coloring of bipartite graphs with and without advice
- Online conflict-free colouring for hypergraphs
- Online graph coloring with advice and randomized adversary (extended abstract)
- Online promise problems with online width metrics
- Parallel and On-Line Graph Coloring
- Randomized online graph coloring
- The Power of Reordering for Online Minimum Makespan Scheduling
Cited in
(13)- Online coloring and a new type of adversary for online graph problems
- A tight bound for online colouring of disk graphs
- scientific article; zbMATH DE number 65708 (Why is no real title available?)
- Online Bounded Coloring of Permutation and Overlap Graphs
- A refined analysis of online path coloring in trees
- Batch coloring of graphs
- 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
- scientific article; zbMATH DE number 742967 (Why is no real title available?)
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)
