Content deleted Content added
→Graph traversal algorithms: Reverted vandalism Tags: Mobile edit Mobile web edit |
|||
Line 82:
* 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}}</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²) on unit weight directed graphs, for both deterministic and randomized algorithms.
==Universal
{{expand section|date=December 2016}}
A '''universal traversal sequence''' is a sequence of instructions comprising a graph traversal for any [[regular graph]] with a set number of vertices and for any starting vertex. A probabilistic proof was used by Aleliunas et al. to show that there exists a universal traversal sequence with number of instructions proportional to <math display="inline">O\left(n^5\right)</math> for any regular graph with ''n'' vertices.<ref>{{cite journal|last1=Aleliunas|first1=R.|last2=Karp|first2=R.|last3=Lipton|first3=R.|last4=Lovász|first4=L.|last5=Rackoff|first5=C.|title=Random walks, universal traversal sequences, and the complexity of maze problems|journal=20th Annual Symposium on Foundations of Computer Science (sfcs 1979)|date=1979|doi=10.1109/SFCS.1979.34}}</ref> The steps specified in the sequence are relative to the current node, not absolute. For example, if the current node is v<sub>j</sub>, and v<sub>j</sub> has ''d'' neighbors, then the traversal sequence will specify the next node to visit, v<sub>j+1</sub>, as the ''i''<sup>th</sup> neighbor of v<sub>j</sub>, where 1 ≤ ''i'' ≤ ''d''.
==References==
| |||