Geodesic
Motion planning in Cartesian product graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 207-221

Voir la notice de l'article provenant de la source Library of Science

Let G be an undirected graph with n vertices. Assume that a robot is placed on a vertex and n − 2 obstacles are placed on the other vertices. A vertex on which neither a robot nor an obstacle is placed is said to have a hole. Consider a single player game in which a robot or obstacle can be moved to adjacent vertex if it has a hole. The objective is to take the robot to a fixed destination vertex using minimum number of moves. In general, it is not necessary that the robot will take a shortest path between the source and destination vertices in graph G. In this article we show that the path traced by the robot coincides with a shortest path in case of Cartesian product graphs. We give the minimum number of moves required for the motion planning problem in Cartesian product of two graphs having girth 6 or more. A result that we prove in the context of Cartesian product of P_n with itself has been used earlier to develop an approximation algorithm for (n^2 − 1)-puzzle
Keywords: robot motion in a graph, Cartesian product of graphs 
@article{DMGT_2014_34_2_a0,
     author = {Deb, Biswajit and Kapoor, Kalpesh},
     title = {Motion planning in {Cartesian} product graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {207--221},
     publisher = {mathdoc},
     volume = {34},
     number = {2},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a0/}
}
TY  - JOUR
AU  - Deb, Biswajit
AU  - Kapoor, Kalpesh
TI  - Motion planning in Cartesian product graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 207
EP  - 221
VL  - 34
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a0/
LA  - en
ID  - DMGT_2014_34_2_a0
ER  - 
%0 Journal Article
%A Deb, Biswajit
%A Kapoor, Kalpesh
%T Motion planning in Cartesian product graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 207-221
%V 34
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a0/
%G en
%F DMGT_2014_34_2_a0
Deb, Biswajit; Kapoor, Kalpesh. Motion planning in Cartesian product graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 207-221. http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a0/