Please use this identifier to cite or link to this item:
Title: Polynomial-time algorithms for path movement problems on trees and unicyclic graphs
Authors: Varin Chouvatut
Wattana Jindaluang
Keywords: Computer Science
Issue Date: 1-Jan-2019
Abstract: © 2019 Taiwan Academic Network Management Committee. All rights reserved. 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.
ISSN: 20794029
Appears in Collections:CMUL: Journal Articles

Files in This Item:
There are no files associated with this item.

Items in CMUIR are protected by copyright, with all rights reserved, unless otherwise indicated.