Constructing competitive tours from local information

DOI10.1016/0304-3975(94)90155-4zbMath0938.68764OpenAlexW2065818036MaRDI QIDQ1331954

Bala Kalyanasundaram, Kirk R. Pruhs

Publication date: 21 June 2000

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

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90155-4

Mathematics Subject Classification ID

Search theory (90B40) Graph theory (including graph drawing) in computer science (68R10)

Related Items (20)

Constructing competitive tours from local information ⋮ Constructing competitive tours from local information ⋮ An improved lower bound for competitive graph exploration ⋮ Competitive online routing in geometric graphs ⋮ Treasure Hunt with Advice ⋮ ONLINE ROUTING IN CONVEX SUBDIVISIONS ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Online graph exploration on trees, unicyclic graphs and cactus graphs ⋮ 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 ⋮ Online Vehicle Routing Problems: A Survey ⋮ A competitive analysis of algorithms for searching unknown scenes ⋮ Online graph exploration algorithms for cycles and trees by multiple searchers ⋮ A parametric simplex algorithm for linear vector optimization problems ⋮ Online searching with an autonomous robot ⋮ Weighted nearest neighbor algorithms for the graph exploration problem on cycles ⋮ The Power of Recourse for Online MST and TSP ⋮ Online traveling salesman problems with service flexibility ⋮ Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The relative neighbourhood graph of a finite planar set
• Not all insertion methods yield constant approximate tours in the Euclidean plane
• Constructing competitive tours from local information
• Spacefilling curves and the planar travelling salesman problem
• How to learn an unknown environment. I
• Dynamic Steiner Tree Problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Competitive Algorithms for Layered Graph Traversal
• Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
• Lower Bounds for Insertion Methods for TSP
• Constructing Reliable Communication Networks of Small Weight Online

This page was built for publication: Constructing competitive tours from local information