Exact Algorithms for Plane Steiner Tree Problems: A Computational Study

Autor:	Pawel Winter, David M. Warme, Martin Zachariasen
Rok vydání:	2000
Předmět:	Discrete mathematics Rectilinear Steiner tree Concatenation Structure (category theory) Steiner tree problem symbols.namesake Exact algorithm Euclidean geometry symbols Mathematics::Metric Geometry Steiner point Algorithm Integer programming Mathematics
Zdroj:	Advances in Steiner Trees ISBN: 9781441948243
DOI:	10.1007/978-1-4757-3171-2_6
Popis:	We present a computational study of exact algorithms for the Euclidean and rectilinear Steiner tree problems in the plane. These algorithms — which are based on the generation and concatenation of full Steiner trees — are much more efficient than other approaches and allow exact solutions of problem instances with more than 2000 terminals. The full Steiner tree generation algorithms for the two problem variants share many algorithmic ideas and the concatenation part is identical (integer programming formulation solved by branch-and-cut). Performance statistics for randomly generated instances, public library instances and “difficult” instances with special structure are presented. Also, results on the comparative performance on the two problem variants are given.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::736f8e79571e24fb1bf9b0ba3f196583 https://doi.org/10.1007/978-1-4757-3171-2_6 Zobrazit plný text záznamu