Počet záznamů: 1
Minimum Spanning Tree of Line Segments
- 1.
SYSNO ASEP 0534907 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV Záznam nebyl označen do RIV Název Minimum Spanning Tree of Line Segments Tvůrce(i) Dey, S. (IN)
Jallu, Ramesh Kumar (UIVT-O) RID, ORCID, SAI
Nandy, S. C. (IN)Celkový počet autorů 3 Zdroj.dok. Computing and Combinatorics. - Cham, 2018 / Wang L. ; Zhu D. - ISSN 0302-9743 - ISBN 78-3-319-94775-4 Rozsah stran s. 529-541 Akce COCOON 2018. International Conference /24./ Datum konání 02.07.2018 - 04.07.2018 Místo konání Qing Dao Země CN - Čína Typ akce WRD Jazyk dok. eng - angličtina Země vyd. CH - Švýcarsko Klíč. slova graphs ; set ; mst ; Minimum spanning tree ; k-MST ; Approximation algorithm ; NP-complete UT WOS 000489763300044 EID SCOPUS 85049678560 DOI 10.1007/978-3-319-94776-1_44 Anotace 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2021
Počet záznamů: 1