Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Motion planning in cartesian product graphs

100%

Deb B., Kapoor K.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 2

207-221

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 Pn with itself has been used earlier to develop an approximation algorithm for (n2 − 1)-puzzle

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Deb B.

1 Kapoor K.

1 2014

Wyniki wyszukiwania

Motion planning in cartesian product graphs