Graph traversal: Difference between revisions

Revision as of 16:57, 7 July 2022

Revision as of 02:51, 8 August 2022

Line 89:

{{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 (SFCS 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==

{{reflist}}

==See also==

* [[External memory graph traversal]]

==References==

{{reflist}}

[[Category:Graph algorithms]]