TY - GEN

T1 - Optimal constrained graph exploration

AU - Duncan, Christian A.

AU - Kobourov, Stephen G.

AU - Anil Kumar, V. S.

PY - 2001

Y1 - 2001

N2 - We address the problem of exploring an unknown graph G = (V, E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length /, then the robot must remain within distance / from the start node s. In the second variation, a fuel tank of limited capacity forces the robot to return to s after traversing C edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot which explores the graph in &Ogr;(|E|) edge traversais. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a &Ogr;(|E|) algorithm. This improves on the previous best known bound of &Ogr;(|E| + \V|2log 2|V|) in [4]. Since the lower bound for the graph exploration problems is |E|, our algorithm is optimal, thus answering the open problem of Awerbuch, Betke, Rivest, and Singh [3].

AB - We address the problem of exploring an unknown graph G = (V, E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length /, then the robot must remain within distance / from the start node s. In the second variation, a fuel tank of limited capacity forces the robot to return to s after traversing C edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot which explores the graph in &Ogr;(|E|) edge traversais. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a &Ogr;(|E|) algorithm. This improves on the previous best known bound of &Ogr;(|E| + \V|2log 2|V|) in [4]. Since the lower bound for the graph exploration problems is |E|, our algorithm is optimal, thus answering the open problem of Awerbuch, Betke, Rivest, and Singh [3].

KW - Algorithms

KW - Design

KW - Performance

KW - Theory

KW - Verification

UR - http://www.scopus.com/inward/record.url?scp=65549083863&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=65549083863&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:65549083863

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 807

EP - 814

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

PB - Association for Computing Machinery (ACM)

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -