Gutenberg Open Science: Computing Euclidean Steiner trees over segments

Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-5792

Full metadata record

DC Field	Value	Language
dc.contributor.author	Althaus, Ernst	-
dc.contributor.author	Rauterberg, Felix	-
dc.contributor.author	Ziegler, Sarah	-
dc.date.accessioned	2021-05-11T08:51:57Z	-
dc.date.available	2021-05-11T08:51:57Z	-
dc.date.issued	2020	-
dc.identifier.uri	https://openscience.ub.uni-mainz.de/handle/20.500.12030/5801	-
dc.description.abstract	In 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.iso	eng	de
dc.rights	CC BY	*
dc.rights.uri	https://creativecommons.org/licenses/by/4.0/	*
dc.subject.ddc	004 Informatik	de_DE
dc.subject.ddc	004 Data processing	en_GB
dc.subject.ddc	510 Mathematik	de_DE
dc.subject.ddc	510 Mathematics	en_GB
dc.title	Computing Euclidean Steiner trees over segments	en_GB
dc.type	Zeitschriftenaufsatz	de
dc.identifier.doi	http://doi.org/10.25358/openscience-5792	-
jgu.type.contenttype	Scientific article	de
jgu.type.dinitype	article	en_GB
jgu.type.version	Published version	de
jgu.type.resource	Text	de
jgu.organisation.department	FB 08 Physik, Mathematik u. Informatik	de
jgu.organisation.number	7940	-
jgu.organisation.name	Johannes Gutenberg-Universität Mainz	-
jgu.rights.accessrights	openAccess	-
jgu.journal.title	EURO journal on computational optimization	de
jgu.journal.volume	8	de
jgu.pages.start	309	de
jgu.pages.end	325	de
jgu.publisher.year	2020	-
jgu.publisher.name	Springer	de
jgu.publisher.place	Berlin u.a.	de
jgu.publisher.uri	https://doi.org/10.1007/s13675-020-00125-w	de
jgu.publisher.issn	2192-4414	de
jgu.organisation.place	Mainz	-
jgu.subject.ddccode	004	de
jgu.subject.ddccode	510	de
jgu.publisher.doi	10.1007/s13675-020-00125-w
jgu.organisation.ror	https://ror.org/023b0x485
Appears in collections:	JGU-Publikationen

Files in This Item:

	File	Description	Size	Format
	althaus_ernst-computing_eucl-20210421124547767.pdf		1.04 MB	Adobe PDF	View/Open

Show simple item record