Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/243204
Type: Artigo de evento
Title: Computing Minimum Dilation Spanning Trees In Geometric Graphs
Author: Brandt
Alex F.; Gaiowski
Miguel F. A. de M.; de Rezende
Pedro J.; de Souza
Cid C.
Abstract: 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.
Subject: Np-hard
Spanners
Country: BERLIN
Editor: SPRINGER-VERLAG BERLIN
Rights: fechado
Identifier DOI: 10.1007/978-3-319-21398-9_24
Address: http://link.springer.com/chapter/10.1007%2F978-3-319-21398-9_24
Date Issue: 2015
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
wos_000363954100024.pdf296.94 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.