scientific article; zbMATH DE number 742967

MaRDI QIDQ4763409zbMATH OpenFDO

Authors Magnús M. Halldórsson, Mario Szegedy

Publication date 11 April 1995

zbMATH Keywords

performance ratiovertex-coloring graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Lower bounds for on-line graph coloring
• Tight bounds for online coloring of basic graph classes
• scientific article; zbMATH DE number 65708
• Tight bounds for online coloring of basic graph classes
• Randomized online graph coloring

Cited in

(20)

• Online coloring and a new type of adversary for online graph problems
• A competitive analysis of the list update problem with lookahead
• A tight bound for online colouring of disk graphs
• A competitive analysis of the list update problem with lookahead
• Online coloring known graphs
• An on-line graph coloring algorithm with sublinear performance ratio
• Circumference, chromatic number and online coloring
• scientific article; zbMATH DE number 65708 (Why is no real title available?)
• Online Bounded Coloring of Permutation and Overlap Graphs
• Lower bounds for on-line graph coloring
• Lower bounds for on-line graph colorings
• On-line approach to off-line coloring problems on graphs with geometric representations
• Online graph coloring against a randomized adversary
• Approximation and online algorithms for multidimensional bin packing: a survey
• Delayed information and action in on-line algorithms
• A still better performance guarantee for approximate graph coloring
• Structural Information and Communication Complexity
• Bounds on partial online list colouring
• The dynamic frequency assignment problem
• Impartial coloring games

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4763409)