Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016)
DOI: 10.7155/jgaa.00421
Lower Bounds for Graph Exploration Using Local Policies
Aditya Kumar Akash,
Sándor Fekete,
Seoung Kyou Lee,
Alejandro López-Ortiz,
Daniela Maftuleac, and
James McLurkin
Vol. 21, no. 3, pp. 371-387, 2017. Regular paper.
Abstract We give lower bounds for various natural node- and edge-based local strategies for exploring a graph.
We consider this problem both in the setting of an arbitrary graph
as well as the abstraction of a geometric exploration of a space
by a robot, both of which have been extensively studied. We consider
local exploration policies that use time-of-last-visit or alternatively
least-frequently-visited local greedy strategies to select the next step
in the exploration path. Both of these strategies were previously considered by Cooper et al. (2011)
for a scenario in which counters for the last visit or visit frequency are attached to
the edges.
In this work we consider
the case in which the counters are associated with the nodes, which for the case
of dual graphs of geometric spaces could be argued to be intuitively more natural and likely more efficient.
Surprisingly, these alternate strategies
give worst-case superpolynomial/exponential time for exploration, whereas the least-frequently-visited
strategy for edges has a polynomially bounded
exploration time, as shown by Cooper et al. (2011).
|
Submitted: May 2016.
Reviewed: November 2016.
Revised: December 2016.
Accepted: December 2016.
Final: January 2017.
Published: February 2017.
|
Journal Supporters
|