Geodesic
Lower Bounds for Graph Exploration Using Local Policies
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation (WALCOM 2016) , Tome 21 (2017) no. 3, pp. 371-387.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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). 
@article{JGAA_2017_21_3_a7,
     author = {Aditya Kumar Akash and S\'andor Fekete and Seoung Kyou Lee and Alejandro L\'opez-Ortiz and Daniela Maftuleac and James McLurkin},
     title = {Lower {Bounds} for {Graph} {Exploration} {Using} {Local} {Policies}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {371--387},
     publisher = {mathdoc},
     volume = {21},
     number = {3},
     year = {2017},
     doi = {10.7155/jgaa.00421},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00421/}
}
TY  - JOUR
AU  - Aditya Kumar Akash
AU  - Sándor Fekete
AU  - Seoung Kyou Lee
AU  - Alejandro López-Ortiz
AU  - Daniela Maftuleac
AU  - James McLurkin
TI  - Lower Bounds for Graph Exploration Using Local Policies
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 371
EP  - 387
VL  - 21
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00421/
DO  - 10.7155/jgaa.00421
LA  - en
ID  - JGAA_2017_21_3_a7
ER  - 
%0 Journal Article
%A Aditya Kumar Akash
%A Sándor Fekete
%A Seoung Kyou Lee
%A Alejandro López-Ortiz
%A Daniela Maftuleac
%A James McLurkin
%T Lower Bounds for Graph Exploration Using Local Policies
%J Journal of Graph Algorithms and Applications
%D 2017
%P 371-387
%V 21
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00421/
%R 10.7155/jgaa.00421
%G en
%F JGAA_2017_21_3_a7
Aditya Kumar Akash; Sándor Fekete; Seoung Kyou Lee; Alejandro López-Ortiz; Daniela Maftuleac; James McLurkin. Lower Bounds for Graph Exploration Using Local Policies. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Tenth International Workshop on Algorithms and Computation  (WALCOM 2016)
					, Tome 21 (2017) no. 3, pp. 371-387. doi : 10.7155/jgaa.00421. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00421/

Cité par Sources :