Constructing competitive tours from local information

DOI10.1007/3-540-56939-1_65zbMath1422.68190OpenAlexW1594646153MaRDI QIDQ4630252

Bala Kalyanasundaram, Kirk R. Pruhs

Publication date: 29 March 2019

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

Full work available at URL: https://doi.org/10.1007/3-540-56939-1_65

zbMATH Keywords

planar graphonline algorithmminimum spanning treeSteiner treeboundary edge

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items

Serving requests with on-line routing, Competitive algorithms for the on-line traveling salesman, Exploring sparse graphs with advice, Not all insertion methods yield constant approximate tours in the Euclidean plane, Competitive on-line coverage of grid environments by a mobile robot

Cites Work

• On-line Steiner trees in the Euclidean plane
• 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
• How to learn an unknown environment. I
• Dynamic Steiner Tree Problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Constructing Reliable Communication Networks of Small Weight Online
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item