Show simple item record

dc.contributor.author
Fritsch, Robin
dc.date.accessioned
2021-07-26T15:08:59Z
dc.date.available
2021-07-26T13:08:38Z
dc.date.available
2021-07-26T15:08:59Z
dc.date.issued
2021-06
dc.identifier.issn
0020-0190
dc.identifier.issn
1872-6119
dc.identifier.other
https://doi.org/10.1016/j.ipl.2021.106096
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/497650
dc.description.abstract
We study the problem of exploring all vertices of an undirected weighted graph that is initially unknown to the searcher. An edge of the graph is only revealed when the searcher visits one of its endpoints. Beginning at some start node, the searcher's goal is to visit every vertex of the graph before returning to the start node on a tour as short as possible. We prove that the Nearest Neighbor algorithm's competitive ratio on trees with n vertices is Ө (log n), i.e. no better than on general graphs. Furthermore, we examine the algorithm Blocking for a range of parameters not considered previously and prove it is 3-competitive on unicyclic graphs as well as 5/2 + √s ≈ 3.91 -competitive on cactus graphs. The best known lower bound for these two graph classes is 2.
en_US
dc.language.iso
en
en_US
dc.publisher
Elsevier
en_US
dc.subject
Graph exploration
en_US
dc.subject
On-line algorithms
en_US
dc.subject
Nearest neighbor
en_US
dc.title
Online Graph Exploration on Trees, Unicyclic Graphs and Cactus Graphs
en_US
dc.type
Journal Article
ethz.journal.title
Information Processing Letters
ethz.journal.volume
168
en_US
ethz.journal.abbreviated
Inf. process. lett.
ethz.pages.start
106096
en_US
ethz.size
6 p.
en_US
ethz.publication.place
Amsterdam
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02140 - Dep. Inf.technologie und Elektrotechnik / Dep. of Inform.Technol. Electrical Eng.::02640 - Inst. f. Technische Informatik und Komm. / Computer Eng. and Networks Lab.::03604 - Wattenhofer, Roger / Wattenhofer, Roger
en_US
ethz.date.deposited
2021-07-26T13:08:43Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2021-07-26T15:09:05Z
ethz.rosetta.lastUpdated
2021-07-26T15:09:05Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Online%20Graph%20Exploration%20on%20Trees,%20Unicyclic%20Graphs%20and%20Cactus%20Graphs&rft.jtitle=Information%20Processing%20Letters&rft.date=2021-06&rft.volume=168&rft.spage=106096&rft.issn=0020-0190&1872-6119&rft.au=Fritsch,%20Robin&rft.genre=article&rft_id=info:doi/https://doi.org/10.1016/j.ipl.2021.106096&
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record