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

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

Abstract

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.

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

BRANDT, Alex Fernando. Exact algorithms for minimum dilation problems in geometric graphs. 2014. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.