Online Graph Exploration: New Results on Old and New Algorithms

DOI10.1007/978-3-642-22012-8_38zbMath1334.68306OpenAlexW4238076645WikidataQ57399767 ScholiaQ57399767MaRDI QIDQ3012942

Pascal Schweitzer, Nicole Megow, Kurt Mehlhorn

Publication date: 7 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (5)

Collaboration Without Communication: Evacuating Two Robots from a Disk ⋮ Collaborative Exploration by Energy-Constrained Mobile Robots ⋮ The Canadian tour operator problem on paths: tight bounds and resource augmentation ⋮ Online graph exploration algorithms for cycles and trees by multiple searchers ⋮ Collaborative exploration of trees by energy-constrained mobile robots

Cites Work

• Unnamed Item
• 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
• 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.
• Optimal constrained graph exploration
• Graph Theory and Probability
• Collective tree exploration
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• 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