Exact and heuristic algorithms for solving difficult problems related to computati...

Send your message by email

Advanced search

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 |

Principal Investigator: | 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. | |