CONSTRUCTING COMPETITIVE TOURS FROM LOCAL INFORMATION

Authors
KALYANASUNDARAM B PRUHS KR
Citation
B. Kalyanasundaram et Kr. Pruhs, CONSTRUCTING COMPETITIVE TOURS FROM LOCAL INFORMATION, Theoretical computer science, 130(1), 1994, pp. 125-138
Citations number
25
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
130
Issue
1
Year of publication
1994
Pages
125 - 138
Database
ISI
SICI code
0304-3975(1994)130:1<125:CCTFLI>2.0.ZU;2-4
Abstract
We consider the problem of a searcher exploring an initially unknown w eighted planar graph G. When the searcher visits a vertex v, it learns of each edge incident to v. The searcher's goal is to visit each vert ex of G, incurring as little cost as possible. We present a constant c ompetitive algorithm for this problem.