Content deleted Content added
m linking |
|||
Line 80:
The problem of graph exploration can be seen as a variant of graph traversal. It is an online problem, meaning that the information about the graph is only revealed during the runtime of the algorithm. A common model is as follows: given a connected graph {{nowrap|1=''G'' = (''V'', ''E'')}} with non-negative edge weights. The algorithm starts at some vertex, and knows all incident outgoing edges and the vertices at the end of these edges—but not more. When a new vertex is visited, then again all incident outgoing edges and the vertices at the end are known. The goal is to visit all ''n'' vertices and return to the starting vertex, but the sum of the weights of the tour should be as small as possible. The problem can also be understood as a specific version of the [[travelling salesman problem]], where the salesman has to discover the graph on the go.
For general graphs, the best known algorithms for both undirected and directed graphs is a simple [[greedy algorithm]]:
* In the undirected case, the greedy tour is at most {{nowrap|''O''(ln ''n'')}}-times longer than an optimal tour.<ref>{{cite journal|last1=Rosenkrantz|first1=Daniel J.|last2=Stearns|first2=Richard E.|last3=Lewis, II|first3=Philip M.|title=An Analysis of Several Heuristics for the Traveling Salesman Problem|journal=SIAM Journal on Computing|volume=6|issue=3|pages=563–581|doi=10.1137/0206041|year=1977}}</ref> The best lower bound known for any deterministic online algorithm is {{nowrap|2.5 − ''ε''}};<ref>{{cite journal|last1=Dobrev|first1=Stefan|last2=Královic|first2=Rastislav|last3=Markou|first3=Euripides|title=Online Graph Exploration with Advice|journal=Proc. Of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO)|volume=7355|pages=267–278|date=2012|doi=10.1007/978-3-642-31104-8_23|series=Lecture Notes in Computer Science|isbn=978-3-642-31103-1}}</ref>
* In the directed case, the greedy tour is at most ({{nowrap|''n'' − 1}})-times longer than an optimal tour. This matches the lower bound of {{nowrap|''n'' − 1}}.<ref>{{cite journal|last1=Foerster|first1=Klaus-Tycho|last2=Wattenhofer|first2=Roger|title=Lower and upper competitive bounds for online directed graph exploration|journal=Theoretical Computer Science|date=December 2016|volume=655|pages=15–29|doi=10.1016/j.tcs.2015.11.017|url=https://zenodo.org/record/895821}}</ref> An analogous competitive lower bound of ''Ω''(''n'') also holds for randomized algorithms that know the coordinates of each node in a geometric embedding. If instead of visiting all nodes just a single "treasure" node has to be found, the competitive bounds are ''Θ''(''n''<sup>2</sup>) on unit weight directed graphs, for both deterministic and randomized algorithms.
| |||