Scholarship 12/17965-6 - Geometria computacional, Otimização combinatória - BV FAPESP
Advanced search
Start date
Betweenand

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 until: November 01, 2012
End date until: 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.

News published in Agência FAPESP Newsletter about the scholarship:
More itemsLess items
Articles published in other media outlets ( ):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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.

Please report errors in scientific publications list using this form.