Title:
|
Computing optimal shortcuts for networks
|
Author:
|
Garijo Royo, Delia; Marquez Pérez, Alberto; Rodríguez, Natalia; Silveira, Rodrigo Ignacio
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. CGA -Computational Geometry and Applications |
Abstract:
|
We augment a plane Euclidean network with a segment or shortcut to minimize the largest distance between any two points along the edges of the resulting network. In this continuous setting, the problem of computing distances and placing a shortcut is much harder as all points on the network, instead of only the vertices, must be taken into account. Our main result for general networks states that it is always possible to determine in polynomial time whether the network has an optimal shortcut and compute one in case of existence. We also improve this general method for networks that are paths, restricted to using two types of shortcuts: those of any fixed direction and shortcuts that intersect the path only on its endpoints. |
Abstract:
|
Peer Reviewed |
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica -Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències -Numerical analysis -Computer science -Anàlisi numèrica -Informàtica -Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry -Classificació AMS::68 Computer science::68Q Theory of computing |
Rights:
|
|
Document type:
|
Article - Published version Conference Object |
Share:
|
|