Polynomial-Time Algorithms for Path Movement Problems on Trees and Unicyclic Graphs

Varin Chouvatut,
Wattana Jindaluang,

Abstract


In the path movement problem, we are given an undirected graph G = (V, E) , a source vertex s , a destination vertex t , and a set of movable objects, called pebbles , which are placed on a subset of the vertices of a graph. We want to move a subset of the pebbles along the edges to a subset of the vertices of the graph such that there exists a path from s to t in graph G in such a way that all the vertices in that path are occupied by at least one pebble. The PathMax and the PathSum problems are the path movement problems in which we want to minimize the maximum movements and the total movements made by the pebbles, respectively. In [7], the researchers proved that both the problems are NP-hard in general graphs. In this paper, the PathMax and the PathSum problems are considered on special classes of graph G , that is, G is a tree and a unicyclic graph. More precisely, this paper shows that PathMax and PathSum problems can be easily solved in polynomial time when the input graph is a tree or a unicyclic graph.


Citation Format:
Varin Chouvatut, Wattana Jindaluang, "Polynomial-Time Algorithms for Path Movement Problems on Trees and Unicyclic Graphs," Journal of Internet Technology, vol. 20, no. 6 , pp. 1729-1735, Nov. 2019.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.





Published by Executive Committee, Taiwan Academic Network, Ministry of Education, Taipei, Taiwan, R.O.C
JIT Editorial Office, Library and Information Center, National Dong Hwa University
No. 1, Sec. 2, Da Hsueh Rd. Shoufeng, Hualien 97401, Taiwan, R.O.C.
Tel: +886-3-931-7017  E-mail: jit.editorial@gmail.com