Given k pairs of terminals {(s_1, t_1),..., (s_k, t_k)} in a graph G, the min-sum k vertex-disjoint paths problem is to find a collection {Q_1,Q_2,... ,Q_k} of vertex-disjoint paths with minimum total length, where Q_i is an s_i-to-t_i path between s_i and t_i. We consider the problem in planar graphs, where little is known about computational tractability, even in restricted cases. Kobayashi and Sommer propose a polynomial-time algorithm for k ≤ 3 in undirected planar graphs assuming all terminals are adjacent to at most two faces. Colin de Verdiere and Schrijver give a polynomial-time algorithm when all the sources are on the boundary of one face and all the sinks are on the boundary of another face and ask about the existence of a polynomial-time algorithm provided all terminals are on a common face. We make progress toward Colin de Verdiere and Schrijver's open question by giving an O(kn~5) time algorithm for undirected planar graphs when {(s_1,t_1),..., (s_k, t_k)} are in counter-clockwise order on a common face.
展开▼
机译：给定图G中的k对终端{{s_1，t_1），...，（s_k，t_k）}，最小和k个顶点不相交的路径问题是找到集合{Q_1，Q_2，... ，Q_k}的顶点不相交路径的总长度最小，其中Q_i是s_i与t_i之间的s_i至t_i路径。我们在平面图中考虑问题，在平面图中，即使在有限的情况下，对计算可处理性的了解也很少。 Kobayashi和Sommer提出了一种无条件平面图中k≤3的多项式时间算法，假设所有终端最多与两个面相邻。当所有源都在一个面的边界上并且所有接收器都在另一面的边界上时，Colin de Verdiere和Schrijver给出多项式时间算法，并询问是否存在多项式时间算法，前提是所有终端都位于一个面的边界上。普通的脸。当{{s_1，t_1），...，（s_k，t_k）}沿逆时针方向排列时，通过为无向平面图提供O（kn〜5）时间算法，我们朝着Colin de Verdiere和Schrijver的开放问题取得了进展在一个普通的脸上。
展开▼
