Graph traversal: Difference between revisions

Revision as of 06:35, 9 June 2023

Revision as of 19:01, 23 July 2023

Line 79:

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|s2cid=14764079 }}</ref> The best lower bound known for any deterministic online algorithm is 10/3.<ref>{{cite journal |last1=Birx |first1=Alexander |last2=Disser |first2=Yann |last3=Hopp |first3=Alexander V. |last4=Karousatou |first4=Christina |title=An improved lower bound for competitive graph exploration |journal=Theoretical Computer Science |date=May 2021 |volume=868 |pages=65–86 |doi=10.1016/j.tcs.2021.04.003|arxiv=2002.10958 |s2cid=211296296 }}</ref>

** Unit weight undirected graphs can be explored with a competitive ration of {{nowrap|2 − ''ε''}},<ref>{{cite journal |last1=Miyazaki |first1=Shuichi |last2=Morimoto |first2=Naoyuki |last3=Okabe |first3=Yasuo |title=The Online Graph Exploration Problem on Restricted Graphs |journal=IEICE Transactions on Information and Systems |date=2009 |volume=E92-D |issue=9 |pages=1620–1627 |doi=10.1587/transinf.E92.D.1620|bibcode=2009IEITI..92.1620M |hdl=2433/226939 |s2cid=8355092 |hdl-access=free }}</ref> which is already a tight bound on [[Tadpole graph|Tadpole graphs]].<ref>{{cite journal |last1=Brandt |first1=Sebastian |last2=Foerster |first2=Klaus-Tycho |last3=Maurer |first3=Jonathan |last4=Wattenhofer |first4=Roger |title=Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs |journal=Theoretical Computer Science |date=November 2020 |volume=839 |pages=176–185 |doi=10.1016/j.tcs.2020.06.007|arxiv=1903.00581 |s2cid=67856035 }}</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|doi-access=free}}</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 (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==