Online graph exploration: New results on old and new algorithms

DOI10.1016/j.tcs.2012.06.034zbMath1269.05103OpenAlexW105334049WikidataQ57399761 ScholiaQ57399761MaRDI QIDQ1929219

Kurt Mehlhorn, Pascal Schweitzer, Nicole Megow

Publication date: 7 January 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.034

zbMATH Keywords

competitive analysisonline algorithmsgraph exploration

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

An improved lower bound for competitive graph exploration ⋮ THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Online graph exploration on trees, unicyclic graphs and cactus graphs ⋮ Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs ⋮ Exploring Endless Space ⋮ Unnamed Item ⋮ The simple grid polygon exploration problem ⋮ The Power of Recourse for Online MST and TSP ⋮ Exploring sparse graphs with advice ⋮ Two-agent tree evacuation ⋮ Convergecast and broadcast by power-aware mobile agents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Online algorithms for searching and exploration in the plane
• Searching in the plane
• Optimal graph exploration without good maps
• Shortest paths without a map
• Impact of memory size on graph exploration capability
• Weighted nearest neighbor algorithms for the graph exploration problem on cycles
• An adversarial queueing model for online server routing
• Online algorithms. The state of the art
• Search games
• Constructing competitive tours from local information
• On the nearest neighbor rule for the traveling salesman problem
• The traveling salesman problem and its variations
• Piecemeal graph exploration by a mobile robot.
• Dynamic cage survey
• Optimal constrained graph exploration
• Graph Theory and Probability
• Collective tree exploration
• Online Vehicle Routing Problems: A Survey
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Arc Routing Problems, Part I: The Chinese Postman Problem
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• On a simple depth-first search strategy for exploring unknown graphs
• Memory Efficient Anonymous Graph Exploration
• Why Robots Need Maps
• Algorithms – ESA 2005
• Smart Robot Teams Exploring Sparse Trees
• Algorithms for the on-line travelling salesman

This page was built for publication: Online graph exploration: New results on old and new algorithms