閱讀全文 | |
篇名 |
Polynomial-Time Algorithms for Path Movement Problems on Trees and Unicyclic Graphs
|
---|---|
並列篇名 | Polynomial-Time Algorithms for Path Movement Problems on Trees and Unicyclic Graphs |
作者 | Varin Chouvatut、Wattana Jindaluang |
英文摘要 | 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. |
起訖頁 | 1729-1735 |
關鍵詞 | Polynomial-time algorithm、Movement problem、Tree、Unicyclic graph |
刊名 | 網際網路技術學刊 |
期數 | 201911 (20:6期) |
出版單位 | 台灣學術網路管理委員會 |
DOI |
|
QR Code | |
該期刊 上一篇
| Cloud-based Personal Data Protection System and its Performance Evaluation |
該期刊 下一篇
| IP Packing Technique for High-speed Firewall Rule Verification |