An on-line graph coloring algorithm with sublinear performance ratio
From MaRDI portal
Publication:1124602
DOI10.1016/0012-365X(89)90096-4zbMATH Open0679.05031MaRDI QIDQ1124602FDOQ1124602
Authors: Michael Saks, William T. Trotter, László Lovász 
Publication date: 1989
Published in: Discrete Mathematics (Search for Journal in Brave)
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- A theory of recursive dimension of ordered sets
- An Effective Version of Dilworth's Theorem
- Title not available (Why is that?)
- On self-organizing sequential search heuristics
- The Linearity of First-Fit Coloring of Interval Graphs
- Effective coloration
- Improving the performance guarantee for approximate graph coloring
- A dynamic location problem for graphs
- Title not available (Why is that?)
- Heuristics That Dynamically Organize Data Structures
- Amortized Computational Complexity
- Title not available (Why is that?)
Cited In (60)
- Primitive recursive reverse mathematics
- Online coloring of short intervals
- Competitive vertex recoloring. (Online disengagement)
- Non-clairvoyant scheduling with conflicts for unit-size jobs
- On the on-line chromatic number of the family of on-line 3-chromatic graphs
- Online unit clustering: Variations on a theme
- Online coloring of bipartite graphs with and without advice
- On the Max Coloring Problem
- Effective on-line coloring of \(P_ 5\)-free graphs
- On the max coloring problem
- Online coloring graphs with high girth and high odd girth
- On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
- Title not available (Why is that?)
- Circumference, chromatic number and online coloring
- Lower bounds for on-line graph coloring
- On the online track assignment problem
- Nonclairvoyant scheduling
- Lower bounds for on-line graph colorings
- An on-line competitive algorithm for coloring \(P_8\)-free bipartite graphs
- Lower bounds for on-line interval coloring with vector and cardinality constraints
- On-line scheduling of jobs with fixed start and end times
- Online promise problems with online width metrics
- On-line load balancing
- On-line approach to off-line coloring problems on graphs with geometric representations
- Online chromatic number is PSPACE-complete
- The on-line first-fit algorithm for radio frequency assignment problems.
- Online graph coloring against a randomized adversary
- Online makespan minimization with parallel schedules
- Optimal on-line coloring of circular arc graphs
- On-line 3-chromatic graphs. II: Critical graphs
- Graphs are not universal for online computability
- Online presentations of finitely generated structures
- On-line coloring of perfect graphs
- Online algorithms for the maximum \(k\)-colorable subgraph problem
- Title not available (Why is that?)
- Adding isolated vertices makes some online algorithms optimal
- The greedy algorithm is optimal for on-line edge coloring
- Colouring bottomless rectangles and arborescences
- Dynamic graph coloring
- On-line coloring \(k\)-colorable graphs
- Performance ratio of the generalized greedy algorithm for \(q\)-coloring problem
- Tight bounds for online coloring of basic graph classes
- Tight bounds for online coloring of basic graph classes
- On-line vertex-covering
- First-fit coloring on interval graphs has performance ratio at least 5
- On-line maximum-order induced hereditary subgraph problems
- Online independent sets.
- Trade-offs in dynamic coloring for bipartite and general graphs
- Online coloring a token graph
- Title not available (Why is that?)
- Online hypergraph coloring
- FOUNDATIONS OF ONLINE STRUCTURE THEORY
- Title not available (Why is that?)
- On-line secret sharing
- On the complexity of injective colorings and its generalizations
- On the Online Unit Clustering Problem
- Online coloring and a new type of adversary for online graph problems
- Online coloring and a new type of adversary for online graph problems
- A structure of punctual dimension two
- An on-line competitive algorithm for coloring bipartite graphs without long induced paths
This page was built for publication: An on-line graph coloring algorithm with sublinear performance ratio
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124602)
