Graph traversal: Difference between revisions

Revision as of 19:01, 23 July 2023

Latest revision as of 19:01, 4 June 2025

(3 intermediate revisions by 2 users not shown)

Line 85:

==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 journalbook|last1=Aleliunas|first1=R.|last2=Karp|first2=R.|last3=Lipton|first3=R.|last4=Lovász|first4=L.|last5=Rackoff|first5=C. |title=20th Annual Symposium on Foundations of Computer Science (SFCS 1979) |chapter=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|s2cid=18719861 }}</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''.

==See also==

Line 94:

{{Graph traversal algorithms}}

{{Data structures and algorithms}}

[[Category:Graph algorithms]]