An on-line graph coloring algorithm with sublinear performance ratio

Recommendations

scientific article; zbMATH DE number 742967
Randomized online graph coloring
On-line and first fit colorings of graphs
Coloring inductive graphs on-line
scientific article; zbMATH DE number 65699

Cites work

scientific article; zbMATH DE number 3900785 (Why is no real title available?)
scientific article; zbMATH DE number 4049076 (Why is no real title available?)
scientific article; zbMATH DE number 3769624 (Why is no real title available?)
A dynamic location problem for graphs
A theory of recursive dimension of ordered sets
Amortized Computational Complexity
An Effective Version of Dilworth's Theorem
Effective coloration
Heuristics That Dynamically Organize Data Structures
Improving the performance guarantee for approximate graph coloring
On self-organizing sequential search heuristics
The Linearity of First-Fit Coloring of Interval Graphs
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms

Cited in

(57)

Online coloring of short intervals
Competitive vertex recoloring. (Online disengagement)
Primitive recursive reverse mathematics
On-line coloring of perfect graphs
Tight bounds for online coloring of basic graph classes
Online coloring a token graph
Effective on-line coloring of $P_ 5$-free graphs
On-line scheduling of jobs with fixed start and end times
On the Online Unit Clustering Problem
Tight bounds for online coloring of basic graph classes
Online hypergraph coloring
On-line vertex-covering
Online coloring and a new type of adversary for online graph problems
Performance ratio of the generalized greedy algorithm for $q$-coloring problem
Online coloring and a new type of adversary for online graph problems
On the online track assignment problem
Colouring bottomless rectangles and arborescences
Optimal on-line coloring of circular arc graphs
The greedy algorithm is optimal for on-line edge coloring
scientific article; zbMATH DE number 4170931 (Why is no real title available?)
On-line maximum-order induced hereditary subgraph problems
On the max coloring problem
Non-clairvoyant scheduling with conflicts for unit-size jobs
Online algorithms for the maximum $k$-colorable subgraph problem
Lower bounds for on-line graph colorings
An on-line competitive algorithm for coloring $P_8$-free bipartite graphs
FOUNDATIONS OF ONLINE STRUCTURE THEORY
Dynamic graph coloring
The on-line first-fit algorithm for radio frequency assignment problems.
Online coloring graphs with high girth and high odd girth
On-line coloring $k$-colorable graphs
On-line secret sharing
Lower bounds for on-line graph coloring
Online promise problems with online width metrics
On the complexity of injective colorings and its generalizations
A structure of punctual dimension two
Online coloring of bipartite graphs with and without advice
Online unit clustering: Variations on a theme
On-line load balancing
On-line 3-chromatic graphs. II: Critical graphs
On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
On-line approach to off-line coloring problems on graphs with geometric representations
On the on-line chromatic number of the family of on-line 3-chromatic graphs
Graphs are not universal for online computability
On the Max Coloring Problem
Online graph coloring against a randomized adversary
First-fit coloring on interval graphs has performance ratio at least 5
An on-line competitive algorithm for coloring bipartite graphs without long induced paths
scientific article; zbMATH DE number 65699 (Why is no real title available?)
Online independent sets.
Online presentations of finitely generated structures
scientific article; zbMATH DE number 65708 (Why is no real title available?)
scientific article; zbMATH DE number 7407778 (Why is no real title available?)
Circumference, chromatic number and online coloring
Trade-offs in dynamic coloring for bipartite and general graphs
Nonclairvoyant scheduling
Lower bounds for on-line interval coloring with vector and cardinality constraints

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)