An on-line graph coloring algorithm with sublinear performance ratio

DOI10.1016/0012-365X(89)90096-4zbMath0679.05031MaRDI QIDQ1124602

László Lovász, William T. jun. Trotter, Michael E. Saks

Publication date: 1989

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

chromatic number; first-fit algorithm; on-line coloring algorithm; on-line graph algorithm

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

Related Items

On-line maximum-order induced hereditary subgraph problems, On the Max Coloring Problem, On the Online Unit Clustering Problem, Online promise problems with online width metrics, Online unit clustering: Variations on a theme, Effective on-line coloring of \(P_ 5\)-free graphs, The greedy algorithm is optimal for on-line edge coloring, On-line coloring \(k\)-colorable graphs, Lower bounds for on-line graph coloring, On-line load balancing, Nonclairvoyant scheduling, On-line scheduling of jobs with fixed start and end times, On-line coloring of perfect graphs, On-line 3-chromatic graphs. II: Critical graphs, On-line vertex-covering, The on-line first-fit algorithm for radio frequency assignment problems., Online independent sets., On the on-line chromatic number of the family of on-line 3-chromatic graphs

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