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

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