New pruning rules for the Steiner tree problem and 2-connected Steiner network problem

Marcus Brazil*, Marcus Volz, Martin Zachariasen, Charl Ras, Doreen Thomas

*Kontaktforfatter for dette arbejde

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

We introduce the concepts of k-lunes and k-lune inequalities, which form the basis for new geometric pruning rules for limiting the number of candidate full components that need to be considered when solving the Euclidean Steiner tree problem or the Euclidean 2-connected Steiner network problem. For the latter problem, these new pruning rules constitute the first empty region properties to have been developed for the problem. We show how to implement these rules efficiently and run computational experiments, indicating the extent to which they can improve the performance of state-of-the-art algorithms for these problems.

OriginalsprogEngelsk
TidsskriftComputational Geometry: Theory and Applications
Vol/bind78
Sider (fra-til)37-49
ISSN0925-7721
DOI
StatusUdgivet - jun. 2019

Fingeraftryk

Steiner network
Steiner Tree Problem
Pruning
Euclidean
Lune
Experiments
Computational Experiments
Limiting

Citer dette

Brazil, Marcus ; Volz, Marcus ; Zachariasen, Martin ; Ras, Charl ; Thomas, Doreen. / New pruning rules for the Steiner tree problem and 2-connected Steiner network problem. I: Computational Geometry: Theory and Applications. 2019 ; Bind 78. s. 37-49.
@article{8461373a990e4c9894d33b5ae7d23841,
title = "New pruning rules for the Steiner tree problem and 2-connected Steiner network problem",
abstract = "We introduce the concepts of k-lunes and k-lune inequalities, which form the basis for new geometric pruning rules for limiting the number of candidate full components that need to be considered when solving the Euclidean Steiner tree problem or the Euclidean 2-connected Steiner network problem. For the latter problem, these new pruning rules constitute the first empty region properties to have been developed for the problem. We show how to implement these rules efficiently and run computational experiments, indicating the extent to which they can improve the performance of state-of-the-art algorithms for these problems.",
keywords = "2-Connected networks, GeoSteiner, Lunes, Pruning rules, Steiner trees",
author = "Marcus Brazil and Marcus Volz and Martin Zachariasen and Charl Ras and Doreen Thomas",
year = "2019",
month = "6",
doi = "10.1016/j.comgeo.2018.10.003",
language = "English",
volume = "78",
pages = "37--49",
journal = "Computational Geometry",
issn = "0925-7721",
publisher = "Elsevier",

}

New pruning rules for the Steiner tree problem and 2-connected Steiner network problem. / Brazil, Marcus; Volz, Marcus; Zachariasen, Martin; Ras, Charl; Thomas, Doreen.

I: Computational Geometry: Theory and Applications, Bind 78, 06.2019, s. 37-49.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - New pruning rules for the Steiner tree problem and 2-connected Steiner network problem

AU - Brazil, Marcus

AU - Volz, Marcus

AU - Zachariasen, Martin

AU - Ras, Charl

AU - Thomas, Doreen

PY - 2019/6

Y1 - 2019/6

N2 - We introduce the concepts of k-lunes and k-lune inequalities, which form the basis for new geometric pruning rules for limiting the number of candidate full components that need to be considered when solving the Euclidean Steiner tree problem or the Euclidean 2-connected Steiner network problem. For the latter problem, these new pruning rules constitute the first empty region properties to have been developed for the problem. We show how to implement these rules efficiently and run computational experiments, indicating the extent to which they can improve the performance of state-of-the-art algorithms for these problems.

AB - We introduce the concepts of k-lunes and k-lune inequalities, which form the basis for new geometric pruning rules for limiting the number of candidate full components that need to be considered when solving the Euclidean Steiner tree problem or the Euclidean 2-connected Steiner network problem. For the latter problem, these new pruning rules constitute the first empty region properties to have been developed for the problem. We show how to implement these rules efficiently and run computational experiments, indicating the extent to which they can improve the performance of state-of-the-art algorithms for these problems.

KW - 2-Connected networks

KW - GeoSteiner

KW - Lunes

KW - Pruning rules

KW - Steiner trees

U2 - 10.1016/j.comgeo.2018.10.003

DO - 10.1016/j.comgeo.2018.10.003

M3 - Journal article

VL - 78

SP - 37

EP - 49

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

ER -