Title of article
Minimum Spanning Tree of Imprecise Points Under L1-metric
Author/Authors
Mesrikhani, Amir Combinatorial and Geometric Algorithms Lab - Department of Computer Science - Yazd University , Farshi, Mohammad Combinatorial and Geometric Algorithms Lab - Department of Computer Science - Yazd University , Iranfar, Behnam Combinatorial and Geometric Algorithms Lab - Department of Computer Science - Yazd University
Pages
12
From page
99
To page
110
Abstract
Let S be a set of imprecise points that is represented by axis-aligned pairwise disjoint squares in the plane. A precise instance of S is a set of points, one from each region of S. In this paper, we study the optimal minimum spanning tree (OptMST) problem on S.
The (OptMST) problem looks for the precise instance of S such that the weight of the MST in this instance, maximize (Max-MST) or minimize (Min-MST) between all precise instances of S under L1-metric. We present a (3/7)-approximation algorithm for Max-MST. This is an improvement on the best-known approximation factor of 1/3.
Keywords
Minimum spanning tree , Imprecise point set , Approximation algorithm
Serial Year
2019
Record number
2496709
Link To Document