论文标题
通用最小曼哈顿网络问题的动态编程方法
Dynamic Programming Approach to the Generalized Minimum Manhattan Network Problem
论文作者
论文摘要
我们研究了广义的最低曼哈顿网络（GMMN）问题：在欧几里得飞机中给出了两对的$ p $，$ \ mathbb {r}^2 $，我们需要找到一个最小长度的几何网络，该网络由轴与nignigned sepgments和$ l_1 $ $ l_1 $ metric（同样是$ l_1 $ calt）组成的最小途径。这个问题通常概括了几个NP硬网络设计问题，这些问题吸收了恒定因子近似算法，例如直线施坦纳树木（RSA）问题，并且开放是GMMN问题是否如此。 作为自下而上的探索，Schnizler（2015）着重于对$ p $的矩形的相交图，并给出了GMMN问题的多项式时时间动态编程算法，其输入受到限制，因此其相交图的最大程度和最大程度。在本文中，作为删除绑定度的第一次尝试，我们为星形案例提供了多项式时间算法，并基于改进的动态编程方法将其扩展到一般树情况。
We study the generalized minimum Manhattan network (GMMN) problem: given a set $P$ of pairs of two points in the Euclidean plane $\mathbb{R}^2$, we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the $L_1$ metric (a so-called Manhattan path) for each pair in $P$. This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in $P$, and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach.
