Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/87218
Title: Weighted Euclidean Steiner Trees for Disaster-Aware Network Design
Authors: Garrote, Luis
Martins, Lúcia
Nunes, Urbano J.
Zachariasen, Martin
Keywords: Euclidean Steiner Tree; Heuristic; Communicantion Networks Reliability
Issue Date: 2019
Publisher: IEEE
Project: CENTRO-01-0145-FEDER-029312 
UID/Multi/00308/2019 
SFRH/BD/88459/2012 
Serial title, monograph or event: 15th International Conference on the Design of Reliable Communication Networks (DRCN 2019)
Place of publication or event: Coimbra, Protugal
Abstract: We consider the problem of constructing a Euclidean Steiner tree in a setting where the plane has been divided into polygonal regions, each with an associated weight. Given a set of points (terminals), the task is to construct a shortest interconnection of the points, where the cost of a line segment in a region is the Euclidean distance multiplied by the weight of the region. The problem is a natural generalization of the obstacle-avoiding Euclidean Steiner tree problem, and has obvious applications in network design. We propose an efficient heuristic strategy for the problem, and evaluate its performance on both randomly generated and near-realistic problem instances. The minimum cost Euclidean Steiner tree can be seen as an optical backbone network (a Spine) avoiding disaster prone areas, here represented as higher cost regions.
URI: http://hdl.handle.net/10316/87218
ISBN: 978-1-5386-8461-0
DOI: 10.1109/DRCN.2019.8713664
Rights: embargoedAccess
Appears in Collections:FCTUC Eng.Electrotécnica - Artigos em Livros de Actas
I&D INESCC - Artigos e Resumos em Livros de Actas

Files in This Item:
File Description SizeFormat Login
DRCN2019_Garrote_Accepted.pdfDRCN 2109, Garrote et al.2.55 MBAdobe PDFEmbargo Access    Request a copy
Show full item record

Page view(s)

86
checked on Sep 11, 2019

Download(s)

7
checked on Sep 11, 2019

Google ScholarTM

Check

Altmetric

Dimensions


This item is licensed under a Creative Commons License Creative Commons