Treffer: Computing optimal shortcuts for networks

Title:
Computing optimal shortcuts for networks
Authors:
Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Garijo Royo, Delia, Marquez Pérez, Alberto, Rodríguez, Natalia, Silveira, Rodrigo Ignacio
Publisher Information:
2018
Document Type:
E-Ressource Electronic Resource
Index Terms:
À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, Conference report
URL:
http://hdl.handle.net/2117/127293
Availability:
Open access content. Open access content
Open Access
Note:
6 p.
application/pdf
English
Other Numbers:
HGF oai:upcommons.upc.edu:2117/127293
Garijo, D., Marquez, A., Rodríguez, N., Silveira, R.I. Computing optimal shortcuts for networks. A: European Workshop on Computational Geometry. "EuroCG 2018: 34th European Workshop on Computational Geometry: Berlin, March 21–23, 2018: extended abstracts". 2018, p. 1-6.
1083259917
Contributing Source:
UNIV POLITECNICA DE CATALUNYA
From OAIster®, provided by the OCLC Cooperative.
Accession Number:
edsoai.on1083259917
Database:
OAIster

Weitere Informationen

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.
Peer Reviewed
Postprint (published version)