Computing minimum 2-edge-connected Steiner networks in the Euclidean plane

Marcus Brazil; Marcus Volz; Martin Zachariasen; Charl Ras; Doreen Thomas

doi:10.1002/net.21835

Computing minimum 2-edge-connected Steiner networks in the Euclidean plane

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

Náttúruvísindadeildin - Faculty of Science and Technology

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

We present a new exact algorithm for computing minimum 2-edge-connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2-edge-connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals—doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2-edge-connected Steiner network problem.

Original language	English
Pages (from-to)	89-103
Number of pages	15
Journal	Networks
Volume	73
Issue number	1
DOIs	https://doi.org/10.1002/net.21835
Publication status	Published - 2019

Keywords

2-connected Steiner networks
2-edge-connected networks
computational geometry
exact algorithm
GeoSteiner
Steiner trees

Access to Document

10.1002/net.21835

Cite this

@article{0c8cc9734f96487b8d84b00402461552,

title = "Computing minimum 2-edge-connected Steiner networks in the Euclidean plane",

abstract = "We present a new exact algorithm for computing minimum 2-edge-connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2-edge-connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals—doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2-edge-connected Steiner network problem.",

keywords = "2-connected Steiner networks, 2-edge-connected networks, computational geometry, exact algorithm, GeoSteiner, Steiner trees",

author = "Marcus Brazil and Marcus Volz and Martin Zachariasen and Charl Ras and Doreen Thomas",

year = "2019",

doi = "10.1002/net.21835",

language = "English",

volume = "73",

pages = "89--103",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "1",

}

TY - JOUR

T1 - Computing minimum 2-edge-connected Steiner networks in the Euclidean plane

AU - Brazil, Marcus

AU - Volz, Marcus

AU - Zachariasen, Martin

AU - Ras, Charl

AU - Thomas, Doreen

PY - 2019

Y1 - 2019

N2 - We present a new exact algorithm for computing minimum 2-edge-connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2-edge-connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals—doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2-edge-connected Steiner network problem.

AB - We present a new exact algorithm for computing minimum 2-edge-connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2-edge-connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals—doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2-edge-connected Steiner network problem.

KW - 2-connected Steiner networks

KW - 2-edge-connected networks

KW - computational geometry

KW - exact algorithm

KW - GeoSteiner

KW - Steiner trees

U2 - 10.1002/net.21835

DO - 10.1002/net.21835

M3 - Article

SN - 0028-3045

VL - 73

SP - 89

EP - 103

JO - Networks

JF - Networks

IS - 1

ER -

Computing minimum 2-edge-connected Steiner networks in the Euclidean plane

Abstract

Keywords

Access to Document

Fingerprint

Cite this