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
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
