MDPProj - Minumum Dilation Problem Project, by P. J. de Rezende, C. C. de Souza, A. F. Brandt and Miguel F. A. de M. Gaiowski

Abstract

The aim of this project is to study and design new techniques for solving the Minimum Dilation Problems. Let P be a set of points in the plane and G(P) be the associated geometric graph, i.e., the complete graph whose vertices correspond to the points in P and whose edges have the Euclidean distance between their endpoints as weights. Let G be a spanning subgraph of G(P). The dilation of a pair of points i and j of P in G is the ratio between the length of the shortest path between i and j in G and their Euclidean distance. The dilation of G is the maximum dilation among all pairs of points in P. The Minimum Dilation Problems (MDP) asks for subgraphs with minimum dilation. Obviously, if G=G(P), (the smallest possible) dilation 1 is obtained. However, in many applications, G must be a proper subgraph of G(P) since there are (positive) costs associated to the inclusion of an edge onto the subgraph G. Common approaches are to limit the number of edges that can be used to build the network or to force it to be in some classes of graphs. While most experimental works published on dilation problems attempt to find (sub)optimal solutions by minimizing other measures than the dilation itself, this project studies some variations aiming to find (sub)optimal solutions with Minimum dilation.

Problem Description

The concept of dilation, then also called stretch factor, can be traced to a paper by Chew [1986] (and its full version Chew [1989]). While Chew's work concerns only about the complete Euclidean graph, the formal definition for arbitrary graph was first, and independently, introduced in Peleg and Ullman [1987] (full version: Peleg and Ullman [1989]).
The former work also coined the term spanners. A t-spanner is a subgraph with dilation less than or equal to t. In this project we aim to find subgraphs, under some restrictions, with the smallest dilation instead of any spanner with bounded stretch factor (t-spanners). Some of these restrictions regards to the number of allowed edges and/or the graph class to which the subgraph belongs, like trees and triangulations. For any of these variations, the problem's input consists of a finite set P of points in the plane, and one seeks to find a subgraph attend some defined characteristics and yields the minimum dilation.

The project developed at UNICAMP deals with following versions of the problem:
  • Minimum Dilation Spanning Tree Problem
  • Minimum Dilation Triangulation Problem

Below, we present details on what has been done and what the current state of the investigation on each of these problems are. We also present benchmarks of instances for the Minimum Dilation Spanning Tree Problem and the Minimum Dilation Triangulation Problem in the following pages.


Minimum Dilation Spanning Tree Problem - MDSTP

The first minimum dilation problem studied by this research group was the MDSTP, whose goal is to find a spanning tree with minimum dilation over a given point set P. This problem is known to be NP-hard and, besides of trying to fulfill the lack of experimental works about this problem, this study aims to find interesting geometric properties that may help to solve others related variants. Unlike other research that has appeared in the literature, the objective here was to design heuristic and exact algorithms.

To read more about our methods for solving the MDSTP and to access downloadable material, click here.

Minimum Dilation Triangulation Problem - MDTP

Since 2013, our group started working on the Minimum Dilation Triangulation Problem (MDTP). As before, we are interested both in heuristic and exact solutions to the MDTP.

To read more about our methods for solving the MDTP and to access downloadable material, click here.


References

  • [1] There is a planar graph almost as good as the complete graph. L. P. Chew. In Proceedings of the 2nd ACM Symposium on Computational Geometry, pages 169–177, 1986.
  • [2] There are planar graphs almost as good as the complete graph. L. P. Chew. Journal of Computer and System Sciences, 39:205–219, 1989.
  • [3] An optimal synchronizer for the hypercube. D. Peleg and J. D. Ullman. In Proceedings of the 8th ACM Symposium on Principles of Distributed Computing, pages 77–85, 1987.
  • [4] An optimal synchronizer for the hypercube. D. Peleg and J. D. Ullman. SIAM Journal on Computing, 18:740–747, 1989.

Contacts



Research supported by: