Graph traversal: Difference between revisions

Revision as of 10:36, 21 March 2019

Revision as of 06:54, 11 June 2019

Line 81:

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. ofOf 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}}</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 traversal sequences==

{{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 {{nowrap|''O''(''n''⁵)}} 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 (sfcsSFCS 1979)|pages=218–223|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''_''j'', and ''v''_''j'' has ''d'' neighbors, then the traversal sequence will specify the next node to visit, ''v''_''j''+1, as the ''i''^th neighbor of ''v''_''j'', where 1 ≤ ''i'' ≤ ''d''.

==References==