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

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.