Minimum Spanning Tree of Line Segments

0534907 - ÚI 2021 CH eng C - Konferenční příspěvek (zahraniční konf.)
Dey, S. - Jallu, Ramesh Kumar - Nandy, S. C.
Minimum Spanning Tree of Line Segments.
Computing and Combinatorics. Cham, 2018 - (Wang, L.; Zhu, D.), s. 529-541. Lecture Notes in Computer Science, 10976. ISBN 78-3-319-94775-4. ISSN 0302-9743.
[COCOON 2018. International Conference /24./. Qing Dao (CN), 02.07.2018-04.07.2018]
Klíčová slova: graphs * set * mst * Minimum spanning tree * k-MST * Approximation algorithm * NP-complete

In this article, we study a variant of the geometric minimum spanning tree (MST) problem. Given a set S of n disjoint line segments in IR2, we need to find a tree spanning one endpoint from each of the segments in S. Note that, we have 2(n) possible choices of such a set of endpoints, each being referred as an instance. Thus, our objective is to choose one among those instances such that the sum of the lengths of all the edges of the tree spanning the points of that instance is minimum. We show that finding such a spanning tree is NP-complete in general, and propose a O(log(2) n)-factor approximation algorithm for the same.
Trvalý link: http://hdl.handle.net/11104/0313050