Premium
Impact of topographic information on graph exploration efficiency
Author(s) -
Panaite Petrişor,
Pelc Andrzej
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200009)36:2<96::aid-net4>3.0.co;2-n
Subject(s) - traverse , graph , a priori and a posteriori , computer science , biconnected graph , theoretical computer science , strength of a graph , knowledge graph , combinatorics , algorithm , line graph , artificial intelligence , mathematics , voltage graph , geography , philosophy , geodesy , epistemology
A robot has to explore an undirected connected graph by visiting all its nodes and traversing all edges. It may either have a complete a priori knowledge of the graph or only have an unoriented map of it, or, finally, lack any knowledge of the graph. We study the impact of this varying amount of knowledge on exploration performance. It is shown that the best exploration algorithm lacking any knowledge of the graph uses twice as many edge traversals in the worst case as does the best algorithm which has an unoriented map of the graph. On the other hand, the latter uses twice as many edge traversals in the worst case as does the best algorithm having a complete knowledge of the graph. Similar results for the restricted case of exploration algorithms working only for trees are also established. © 2000 John Wiley & Sons, Inc.