scientific article; zbMATH DE number 742967

zbMATH Open0829.68096MaRDI QIDQ4763409FDOQ4763409

Magnús M. Halldórsson, Mario Szegedy

Publication date: 11 April 1995

Title of this publication is not available (Why is that?)

Recommendations

• Lower bounds for on-line graph coloring
• Tight bounds for online coloring of basic graph classes
• scientific article
• Tight bounds for online coloring of basic graph classes
• Randomized online graph coloring

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)

Cited In (18)

• 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
• Title not available (Why is that?)
• Circumference, chromatic number and online coloring
• Online Bounded Coloring of Permutation and Overlap Graphs
• Lower bounds for on-line graph coloring
• On-line approach to off-line coloring problems on graphs with geometric representations
• 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
• A Competitive analysis of the list update problem with lookahead
• The dynamic frequency assignment problem
• Impartial coloring games
• Online coloring and a new type of adversary for online graph problems

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)