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

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
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?)
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

(62)

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
Online algorithms for the maximum $k$-colorable subgraph problem
Non-clairvoyant scheduling with conflicts for unit-size jobs
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
Graphs are not universal for online computability
Online presentations of finitely generated structures
Tight bounds for online coloring of basic graph classes
Online coloring a token graph
Circumference, chromatic number and online coloring
Trade-offs in dynamic coloring for bipartite and general graphs
Performance ratio of the generalized greedy algorithm for q-coloring problem
Lower bounds for on-line graph colorings
An on-line competitive algorithm for coloring P₈-free bipartite graphs
Lower bounds for on-line interval coloring with vector and cardinality constraints
Online graph coloring against a randomized adversary
scientific article; zbMATH DE number 4170931 (Why is no real title available?)
On the complexity of injective colorings and its generalizations
scientific article; zbMATH DE number 65699 (Why is no real title available?)
scientific article; zbMATH DE number 65708 (Why is no real title available?)
On the online track assignment problem
On-line maximum-order induced hereditary subgraph problems
Optimal on-line coloring of circular arc graphs
On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
Online coloring of bipartite graphs with and without advice
First-fit coloring on interval graphs has performance ratio at least 5
A structure of punctual dimension two
Tight bounds for online coloring of basic graph classes
Foundations of online structure theory. II: The operator approach
FOUNDATIONS OF ONLINE STRUCTURE THEORY
An on-line competitive algorithm for coloring bipartite graphs without long induced paths
On the Max Coloring Problem
On the Online Unit Clustering Problem
Dynamic graph coloring
Online coloring and a new type of adversary for online graph problems
Online coloring and a new type of adversary for online graph problems
Primitive recursive reverse mathematics
Competitive vertex recoloring. (Online disengagement)
Colouring bottomless rectangles and arborescences
Online coloring of short intervals
On-line secret sharing
Tree coloring with predictions
Incorporating predictions in online graph coloring algorithms
On the max coloring problem
Online graph coloring with predictions
On-line approach to off-line coloring problems on graphs with geometric representations
First-fit coloring of forests in random arrival model
Defective and clustered colouring of graphs with given girth
Online promise problems with online width metrics
Online unit clustering: Variations on a theme
Online coloring graphs with high girth and high odd girth
Online hypergraph coloring

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)