Exploring an unknown graph
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 355-361
- https://doi.org/10.1109/fscs.1990.89554
Abstract
It is desired to explore all edges of an unknown directed, strongly connected graph. At each point one has a map of all nodes and edges visited, one can recognize these nodes and edges upon seeing them again, and it is known how many unexplored edges emanate from each node visited. The goal is to minimize the ratio of the total number of edges traversed to the optimum number of traversals had the graph been known. For Eulerian graphs this ratio cannot be better than 2, and 2 is achievable by a simple algorithm. In contrast, the ratio is unbounded when the deficiency of the graph (the number of edges that have to be added to make it Eulerian) is unbounded. The main result is an algorithm that achieves a bounded ratio when the deficiency is bounded; unfortunately the ratio is exponential in the deficiency. It is also shown that, when partial information about the graph is available, minimizing the worst-case ratio is PSPACE-complete.<>Keywords
This publication has 4 references indexed in Scilit:
- Inference of finite automata using homing sequencesPublished by Association for Computing Machinery (ACM) ,1989
- Competitive snoopy cachingAlgorithmica, 1988
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985
- Matching, Euler tours and the Chinese postmanMathematical Programming, 1973