Graph traversal: Difference between revisions

Revision as of 15:54, 31 December 2020

Revision as of 17:18, 6 June 2021

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|210/3.5 − ''ε''}};<ref>{{cite journal |last1=DobrevBirx |first1=StefanAlexander |last2=KrálovicDisser |first2=RastislavYann |last3=MarkouHopp |first3=EuripidesAlexander V. |titlelast4=OnlineKarousatou Graph|first4=Christina Exploration with Advice|journaltitle=Proc.An Ofimproved thelower 19thbound Internationalfor Colloquiumcompetitive ongraph Structuralexploration Information|journal=Theoretical andComputer CommunicationScience Complexity|date=May 2021 (SIROCCO)|volume=7355868 |pages=267–278|date=201265–86 |doi=10.10071016/978-3-642-31104-8_23|series=Lecture Notes in Computer Science|isbn=978-3-642-31103-1j.tcs.2021.04.003}}</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}}</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}}</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.