Advanced search
Start date

Dual bounds and exact algorithms for minimum dilation problems in geometric graphs

Grant number: 12/17965-6
Support type:Scholarships in Brazil - Master
Effective date (Start): November 01, 2012
Effective date (End): July 31, 2014
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Cid Carvalho de Souza
Grantee:Alex Fernando Brandt
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil


This project aims to produce a dissertation to be developed in theMasters Program in Computer Science at UNICAMP, whose research topicis the minimum dilation problem in geometric graphs. This is aspecial case of network design with good connections at low cost, aproblem frequently found in practical situations. This researchproject investigates the situation in which it is desired to obtain anetwork that connect a given set of points in the plane to minimizethe dilation (best quality) using few edges (low cost). Given a pointset P = {p1, p2, ..., pn} in the plane. The geometric graph G(P)associated with P is defined as the undirected complete edge-weightedgraph with n vertices, where the weight of an edge corresponds to theEuclidean distance between the points represented by their ends. Theobjective is to find a generator subgraph G of G (P) that minimizesthe worst-case ratio between the lengths of shortest paths in G andG(P) for any pair of vertex of the graph, called dilation of G.Should be examined cases where the designed network is a simpleconnected graph G with n-1+k edges, with k greater or equal to 0.Special attention is given to the case where k = 0 and G is a spanningtree. Our approach uses Lagrangian and linear relaxations and exactalgorithms to find dual bounds and optimal solutions.