Finding Paths with Minimum Shared Edges in Graphs with Bounded Treewidth
Finding Paths with Minimum Shared Edges in Graphs with Bounded Treewidth
复制标题
在有界树宽的图中查找具有最小共享边的路径
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
X. Zhou
中科院分区：
文献类型：
--
作者：
Zhiqian Ye;Y.;Huazhong Lu;X. Zhou
- 给定一个正整数P，图G和一对两个端子S和T中的两个端子S和T，最小的共享边路路径问题是找到连接S和T的P路径，以最大程度地减少路径之间共享的边缘数量。在本文中，我们最多可以证明，对于给定的两个终端的最小共享路径问题可以在多项式时间内解决具有界限的图形。
— Given a positive integer p , a graph G and a pair of two terminals s and t in G , the minimum shared-edge paths problem is to find p paths connecting s and t so as to minimize the number of edges shared among the paths. This is a generalization of the well-known edge-disjoint paths problem which asks whether there exist p pairwise edge-disjoint paths connecting the terminals. The edge-disjoint paths problem is NP-complete for given many pairs of terminals even for graphs with treewidth at most two. In this paper we show that the minimum shared-edge paths problem for a given pair of two terminals can be solved in polynomial time for graphs with bounded treewidth.