Optimal Path Cover for Graphs of Small Treewidth
Zhe Nie, Yueping Li, Xiaohong Zhou · 2008
This paper studies the optimal path cover problem in graphs of small treewidth. Let G=(V, E) be a graph modeled by network with vertex set V and edge set E. Given a specified vertex set SVsubeV(G), a path cover is a path P of G such that SVsubeV(P). A path cover PC is optimal if the cost of PC is minimum. Optimal path cover problem is essential in the route design, especially, when the group broadcast is applied. Optimal path cover problem is NP-hard in general graphs. Since the graph representing the modern communication network has small treewidth, we restrict the problem in small treewidth graphs. Suppose the treewidth of G is k. We present an algorithm for the optimal path cover problem. Its time complexity isO(|V|2k*k!) in the worst case.