Route-Enabling Graph Orientation Problems
Route-Enabling Graph Orientation Problems
复制标题
路由启用图方向问题
DOI：
10.1007/s00453-011-9589-z
复制
发表时间：
2013
期刊：
影响因子：
1.1
通讯作者：
Ryuhei Uehara
中科院分区：
文献类型：
--
作者：
Takehiro Ito;Yuichiro Miyamoto;Hirotaka Ono;Hisao Tamaki;Ryuhei Uehara
给定一个无向边权重图G和一组有序顶点对(称为ST-对)，我们考虑了求所有边的方向的两个问题：最小和定向是最小化所有ST对之间的最短有向距离之和；最小-最大定向是最小化所有ST对之间的最大最短有向距离。注意，这些用于ST对的最短有向路径不一定是边不相交的。在这篇文章中，我们首先证明了这两个问题对于平面图来说是强NP-难的，即使所有边权都相同，并且这两个问题对于圈都可以在多项式时间内求解。然后我们考虑仅限于仙人掌的问题，仙人掌形成了一个包含树和圈的图类，但它是平面图的一个子类。然后，最小和方向在多项式时间内是可解的，而最小-最大方向即使对两对也是NP难的。然而，基于Lp-松弛，我们提出了一种多项式时间的2-近似算法来形成最大方向。最后，我们给出了当ST对的个数为固定常数时，仙人掌上的最大定向的完全多项式时间逼近格式(FPTAS)。
Given an undirected and edge-weighted graphGtogether with a set of ordered vertex-pairs, calledst-pairs, we consider two problems of finding an orientation of all edges inG:min-sum orientationis to minimize the sum of the shortest directed distances between allst-pairs; andmin-max orientationis to minimize the maximum shortest directed distance among allst-pairs. Note that these shortest directed paths forst-pairs are not necessarily edge-disjoint. In this paper, we first show that both problems are strongly NP-hard for planar graphs even if all edge-weights are identical, and that both problems can be solved in polynomial time for cycles. We then consider the problems restricted to cacti, which form a graph class that contains trees and cycles but is a subclass of planar graphs. Then,min-sum orientationis solvable in polynomial time, whereasmin-max orientationremains NP-hard even for twost-pairs. However, based on LP-relaxation, we present a polynomial-time 2-approximation algorithm formin-max orientation. Finally, we give a fully polynomial-time approximation scheme (FPTAS) formin-max orientationon cacti if the number ofst-pairs is a fixed constant.