Actas de congresos
Computing Minimum Dilation Spanning Trees In Geometric Graphs
Registro en:
978-3-319-21398-9; 978-3-319-21397-2
Computing Minimum Dilation Spanning Trees In Geometric Graphs. Springer-verlag Berlin, v. 9198, p. 297-309 2015.
0302-9743
WOS:000363954100024
10.1007/978-3-319-21398-9_24
Autor
Brandt
Alex F.; Gaiowski
Miguel F. A. de M.; de Rezende
Pedro J.; de Souza
Cid C.
Institución
Resumen
Let P be a set of points in the plane and G(P) be the associated geometric graph. Let T be a spanning tree of G(P). The dilation of a pair of points i and j of P in T is the ratio between the length of the path between i and j in T and their Euclidean distance. The dilation of T is the maximum dilation among all pairs of points in P. The minimum dilation spanning tree problem (MDSTP) asks for a tree with minimum dilation. So far, no exact algorithm has been proposed in the literature to compute optimal solutions to the MDSTP. This paper aims at filling this gap. To this end, we developed an algorithm that combines an integer programming model, a geometric preprocessing and an efficient heuristic for the MDSTP. We report on computational tests in which, for the first time, instances of up to 20 points have been solved to proven optimality. 9198
297 309