An on-line graph coloring algorithm with sublinear performance ratio
From MaRDI portal
Publication:1124602
DOI10.1016/0012-365X(89)90096-4zbMath0679.05031MaRDI QIDQ1124602
László Lovász, Michael E. Saks, William T. jun. Trotter
Publication date: 1989
Published in: Discrete Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items (52)
Online makespan minimization with parallel schedules ⋮ Lower bounds for on-line graph coloring ⋮ On-line load balancing ⋮ Nonclairvoyant scheduling ⋮ On-line scheduling of jobs with fixed start and end times ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Adding isolated vertices makes some greedy online algorithms optimal ⋮ Online algorithms for the maximum \(k\)-colorable subgraph problem ⋮ Online promise problems with online width metrics ⋮ On the on-line chromatic number of the family of on-line 3-chromatic graphs ⋮ On-line coloring of perfect graphs ⋮ On-line 3-chromatic graphs. II: Critical graphs ⋮ Lower Bounds for On-line Graph Colorings ⋮ An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs ⋮ On the complexity of injective colorings and its generalizations ⋮ Graphs are not universal for online computability ⋮ Primitive recursive reverse mathematics ⋮ Competitive vertex recoloring. (Online disengagement) ⋮ Colouring bottomless rectangles and arborescences ⋮ A structure of punctual dimension two ⋮ On the online track assignment problem ⋮ Online coloring of short intervals ⋮ Trade-offs in dynamic coloring for bipartite and general graphs ⋮ Lower Bounds for On-line Interval Coloring with Vector and Cardinality Constraints ⋮ Online presentations of finitely generated structures ⋮ Circumference, chromatic number and online coloring ⋮ Non-clairvoyant scheduling with conflicts for unit-size jobs ⋮ Tight bounds for online coloring of basic graph classes ⋮ Effective on-line coloring of \(P_ 5\)-free graphs ⋮ On-line secret sharing ⋮ Online coloring of bipartite graphs with and without advice ⋮ Online unit clustering: Variations on a theme ⋮ An on-line competitive algorithm for coloring bipartite graphs without long induced paths ⋮ On the max coloring problem ⋮ The greedy algorithm is optimal for on-line edge coloring ⋮ Online coloring graphs with high girth and high odd girth ⋮ Online hypergraph coloring ⋮ On-line vertex-covering ⋮ On-line maximum-order induced hereditary subgraph problems ⋮ On the Max Coloring Problem ⋮ On the Online Unit Clustering Problem ⋮ Dynamic graph coloring ⋮ Online chromatic number is PSPACE-complete ⋮ Online coloring and a new type of adversary for online graph problems ⋮ On-line coloring \(k\)-colorable graphs ⋮ Online coloring a token graph ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Tight Bounds for Online Coloring of Basic Graph Classes ⋮ Unnamed Item ⋮ The on-line first-fit algorithm for radio frequency assignment problems. ⋮ Online independent sets. ⋮ Online coloring and a new type of adversary for online graph problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A dynamic location problem for graphs
- A theory of recursive dimension of ordered sets
- Amortized Computational Complexity
- Improving the performance guarantee for approximate graph coloring
- The Linearity of First-Fit Coloring of Interval Graphs
- An Effective Version of Dilworth's Theorem
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- On self-organizing sequential search heuristics
- Effective coloration
- Heuristics That Dynamically Organize Data Structures
This page was built for publication: An on-line graph coloring algorithm with sublinear performance ratio
