Advice complexity of the online coloring problem

DOI10.1007/978-3-642-38233-8_29MaRDI QIDQ4924664zbMATH OpenOpenAlexFDO

Authors Sebastian Seibert, Andreas Sprock, Walter Unger

Publication date 7 June 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/20.500.11850/156343

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Advice complexity of online coloring for paths
• Online coloring of bipartite graphs with and without advice
• Online coloring of bipartite graphs with and without advice
• On the advice complexity of coloring bipartite graphs and two-colorable hypergraphs
• Optimal online edge coloring of planar graphs with advice

Cited in

(23)

• The advice complexity of a class of hard online problems
• On the advice complexity of the online dominating set problem
• Online multi-coloring with advice
• Distributed computing with advice: information sensitivity of graph coloring
• Online bin packing with advice
• Online graph coloring with advice and randomized adversary (extended abstract)
• Advice complexity of online coloring for paths
• Online coloring of bipartite graphs with and without advice
• A technique to obtain hardness results for randomized online algorithms -- a survey
• Optimal online edge coloring of planar graphs with advice
• On energy-efficient computations with advice
• Online Multi-Coloring with Advice
• On the advice complexity of coloring bipartite graphs and two-colorable hypergraphs
• Online coloring of bipartite graphs with and without advice
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles
• On the advice complexity of the \(k\)-server problem under sparse metrics
• Distributed Computing with Advice: Information Sensitivity of Graph Coloring
• Towards using the history in online computation with advice
• Online Minimum Spanning Tree with Advice
• Online L(2,1)-coloring problem on paths with restricted size of memory
• Fully Online Matching with Advice on General Bipartite Graphs and Paths
• Tree coloring with predictions
• On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles

This page was built for publication: Advice complexity of the online coloring problem

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