Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-5792
Full metadata record
DC FieldValueLanguage
dc.contributor.authorAlthaus, Ernst-
dc.contributor.authorRauterberg, Felix-
dc.contributor.authorZiegler, Sarah-
dc.date.accessioned2021-05-11T08:51:57Z-
dc.date.available2021-05-11T08:51:57Z-
dc.date.issued2020-
dc.identifier.urihttps://openscience.ub.uni-mainz.de/handle/20.500.12030/5801-
dc.description.abstractIn the classical Euclidean Steiner minimum tree (SMT) problem, we are given a set of points in the Euclidean plane and we are supposed to find the minimum length tree that connects all these points, allowing the addition of arbitrary additional points. We investigate the variant of the problem where the input is a set of line segments. We allow these segments to have length 0, i.e., they are points and hence we generalize the classical problem. Furthermore, they are allowed to intersect such that we can model polygonal input. As in the GeoSteiner approach of Juhl et al. (Math Program Comput 10(2):487–532, 2018) for the classical case, we use a two-phase approach where we construct a superset of so-called full components of an SMT in the first phase. We prove a structural theorem for these full components, which allows us to use almost the same GeoSteiner algorithm as in the classical SMT problem. The second phase, the selection of a minimal cost subset of constructed full components, is exactly the same as in GeoSteiner approach. Finally, we report some experimental results that show that our approach is more efficient than the approximate solution that is obtained by sampling the segments.en_GB
dc.language.isoengde
dc.rightsCC-BY*
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/*
dc.subject.ddc004 Informatikde_DE
dc.subject.ddc004 Data processingen_GB
dc.subject.ddc510 Mathematikde_DE
dc.subject.ddc510 Mathematicsen_GB
dc.titleComputing Euclidean Steiner trees over segmentsen_GB
dc.typeZeitschriftenaufsatzde
dc.identifier.doihttp://doi.org/10.25358/openscience-5792-
jgu.type.contenttypeScientific articlede
jgu.type.dinitypearticleen_GB
jgu.type.versionPublished versionde
jgu.type.resourceTextde
jgu.organisation.departmentFB 08 Physik, Mathematik u. Informatikde
jgu.organisation.number7940-
jgu.organisation.nameJohannes Gutenberg-Universität Mainz-
jgu.rights.accessrightsopenAccess-
jgu.journal.titleEURO journal on computational optimizationde
jgu.journal.volume8de
jgu.pages.start309de
jgu.pages.end325de
jgu.publisher.year2020-
jgu.publisher.nameSpringerde
jgu.publisher.placeBerlin u.a.de
jgu.publisher.urihttps://doi.org/10.1007/s13675-020-00125-wde
jgu.publisher.issn2192-4414de
jgu.organisation.placeMainz-
jgu.subject.ddccode004de
jgu.subject.ddccode510de
Appears in collections:JGU-Publikationen

Files in This Item:
File Description SizeFormat 
althaus_ernst-computing_eucl-20210421124547767.pdf1.04 MBAdobe PDFView/Open