On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods
On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods
复制标题
DOI：
10.1007/s00224-014-9591-3
复制
发表时间：
2014-11
影响因子：
0.5
通讯作者：
Reza Dorrigiv;Robert Fraser;Meng He;Shahin Kamali;A. Kawamura;A. López-Ortiz;Diego Seco
中科院分区：
文献类型：
--
作者：
Reza Dorrigiv;Robert Fraser;Meng He;Shahin Kamali;A. Kawamura;A. López-Ortiz;Diego Seco
研究了不精确数据下的欧氏最小生成树问题。为了模拟不精确性，我们接受一组平面上不相交的圆盘作为输入。从集合的每个成员中，必须选择一个点，并且在所选择的点的集合上计算MST。我们考虑最小化和最大化MST在输入上的权重。该问题的最小权重版本被称为具有邻域的最小生成树（MSPs）问题，而最大权重版本（max-MSPs）以前没有被研究过。我们给出了最大-最小问题的确定性和参数化近似算法，以及最小问题的参数化算法。此外，我们提出了硬度的近似证明这两种设置。
We study optimization problems for the Euclidean Minimum Spanning Tree (MST) problem on imprecise data. To model imprecision, we accept a set of disjoint disks in the plane as input. From each member of the set, one point must be selected, and the MST is computed over the set of selected points. We consider both minimizing and maximizing the weight of the MST over the input. The minimum weight version of the problem is known as the Minimum Spanning Tree with Neighborhoods (MSTN) problem, and the maximum weight version (max-MSTN) has not been studied previously to our knowledge. We provide deterministic and parameterized approximation algorithms for themax-MSTN problem, and a parameterized algorithm for the MSTN problem. Additionally, we present hardness of approximation proofs for both settings.