Online Graph Exploration with Advice

DOI10.1007/978-3-642-31104-8_23zbMath1504.68162OpenAlexW1884349932WikidataQ57310484 ScholiaQ57310484MaRDI QIDQ2913217

Rastislav Královič, Euripides Markou, Stefan Dobrev

Publication date: 26 September 2012

Published in: Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31104-8_23

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Related Items (19)

An improved lower bound for competitive graph exploration ⋮ Online Graph Coloring Against a Randomized Adversary ⋮ Treasure Hunt with Advice ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Online graph exploration on trees, unicyclic graphs and cactus graphs ⋮ A Technique to Obtain Hardness Results for Randomized Online Algorithms – A Survey ⋮ Optimal Online Edge Coloring of Planar Graphs with Advice ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs ⋮ Unnamed Item ⋮ Advice complexity of adaptive priority algorithms ⋮ Online search with a hint ⋮ On the advice complexity of the \(k\)-server problem under sparse metrics ⋮ Online graph exploration algorithms for cycles and trees by multiple searchers ⋮ Online Minimum Spanning Tree with Advice ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Exploring sparse graphs with advice ⋮ On Advice Complexity of the k-server Problem under Sparse Metrics ⋮ Online bin packing with advice

This page was built for publication: Online Graph Exploration with Advice