Article
Shortcut sets for the locus of plane Euclidean networks
Author/s | Cáceres, José
Garijo Royo, Delia ![]() ![]() ![]() ![]() ![]() ![]() ![]() González, Antonio Márquez Pérez, Alberto ![]() ![]() ![]() ![]() ![]() ![]() ![]() Puertas, María Luz Ribeiro, Paula |
Department | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Publication Date | 2018 |
Deposit Date | 2020-06-21 |
Published in |
|
Abstract | We study the problem of augmenting the locus N of a plane Euclidean network N by in- serting iteratively a finite set of segments, called shortcut set , while reducing the diameterof the locus of the resulting network. ... We study the problem of augmenting the locus N of a plane Euclidean network N by in- serting iteratively a finite set of segments, called shortcut set , while reducing the diameterof the locus of the resulting network. There are two main differences with the classicalaugmentation problems: the endpoints of the segments are allowed to be points of N as well as points of the previously inserted segments (instead of only vertices of N ), and the notion of diameter is adapted to the fact that we deal with N instead of N . This increases enormously the hardness of the problem but also its possible practical applications to net- work design. Among other results, we characterize the existence of shortcut sets, computethem in polynomial time, and analyze the role of the convex hull of N when inserting a shortcut set. Our main results prove that, while the problem of minimizing the size of ashortcut set is NP-hard, one can always determine in polynomial time whether insertingonly one segment suffices to reduce the diameter. |
Funding agencies | Ministerio de Economía y Competitividad (MINECO). España |
Project ID. | MTM2015-63791-R
![]() |
Citation | Cáceres, J., Garijo Royo, D., González, A., Márquez Pérez, A., Puertas, M.L. y Ribeiro, P. (2018). Shortcut sets for the locus of plane Euclidean networks. Applied Mathematics and Computation, 334 (october 2018), 192-205. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Shortcut sets for the locus of ... | 689.1Kb | ![]() | View/ | |