Weighted nearest neighbor algorithms for the graph exploration problem on cycles

DOI10.1016/j.ipl.2009.10.013zbMath1206.68369OpenAlexW2032799093MaRDI QIDQ990116

Takuro Yoshimuta, Shuichi Miyazaki, Yuichi Asahiro, Eiji Miyano

Publication date: 2 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2009.10.013

zbMATH Keywords

competitive ratioon-line algorithmsgraph exploration problemweighted nearest neighbor

Mathematics Subject Classification ID

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

Related Items

An improved lower bound for competitive graph exploration ⋮ Online graph exploration: New results on old and new algorithms ⋮ Online graph exploration on a restricted graph class: optimal solutions for tadpole graphs ⋮ Online Graph Exploration: New Results on Old and New Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Shortest paths without a map
• Impact of memory size on graph exploration capability
• Constructing competitive tours from local information
• The Polygon Exploration Problem
• How to learn an unknown environment. I
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• ONLINE ROUTING IN CONVEX SUBDIVISIONS
• Tree exploration with little memory
• Exploring Unknown Environments
• Algorithms – ESA 2005
• Algorithms for the on-line travelling salesman