A New Minimum Cost Flow Algorithm with Applications to Graph Drawing
A New Minimum Cost Flow Algorithm with Applications to Graph Drawing
复制标题
一种新的最小成本流算法及其在绘图中的应用
DOI：
10.1007/3-540-62495-3_49
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
R. Tamassia
中科院分区：
文献类型：
--
作者：
Ashim Garg;R. Tamassia
让我们建立一个无节点、无标记、无正电弧成本的单源单汇流网络。我们提出了一种伪多项式算法，该算法计算了在时间0 （χ3/4m√logn）内代价最小的最大流，其中χ为流的代价。这改进了以前已知的网络方法，其中流的最小成本很小。我们还展示了流算法在一个众所周知的图形绘制问题中的应用。也就是说，我们展示了如何在时间o （n7/4√logn）内计算一个具有最小弯曲数的平面正交图。这是第一个弯曲最小化的次二次算法。这个问题之前的最佳边界是o (n2logn)[19]。
LetNbe a single-source single-sink flow network withnnodes,marcs, and positive arc costs. We present a pseudo-polynomial algorithm that computes a maximum flow of minimum cost forNin timeO(χ3/4m√logn), whereχis the cost of the flow. This improves upon previously known methods for networks where the minimum cost of the flow is small. We also show an application of our flow algorithm to a well-known graph drawing problem. Namely, we show how to compute a planar orthogonal drawing with the minimum number of bends for ann- vertex embedded planar graph in timeO(n7/4√logn). This is the first subquadratic algorithm for bend minimization. The previous best bound for this problem wasO(n2logn) [19].