Instituto de Computação - UNICAMP
Return to project main page
The second part is a sequence of n identifiers and points coordinates. Each vertex is indexed by a (increasing) integer, starting from zero, and is represented by its x and y coordinates each of which is written with six decimal places.
Finally, the third part is a list of (allowed) edges described by the its endpoints' indexes and its length. The length is presented rounded to six decimal places to avoid pitfalls and to facilitate comparisons. The list end is marked by the negative integer -1.
Any blank line or started by a '#' is considered as comments and is discarded. As an example, here is the representation of the vertices of a square with coordinates (10, 0) (0, 10) (-10, 0) and (0, -10):
There is a total of 180 MDSTP instances, each one having between 10 and 20 points, all with the complete set of edges allowed:
Universidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail:
MDSTP - Minumum Dilation Spanning Tree Problem, by P. J. de Rezende, C. C. de Souza, A. F. Brandt and Miguel F. A. de M. Gaiowski
Citing this page:
-
Use the BibTeX entry:
@Misc{art-gallery-instances-page,
author = {Pedro J. de Rezende and Cid C. de Souza and Aléx. F. Brandt and Miguel F. A. de M. Gaiowski},
title = {The {Minimum Dilation Problem} Project},
year = {2014},
note = {\sl{www.ic.unicamp.br/$\sim$cid/Problem-instances/Dilation}}
}
File Format: Instances
Each file consists of three parts. The first part is an integer value n that represents the number of points.The second part is a sequence of n identifiers and points coordinates. Each vertex is indexed by a (increasing) integer, starting from zero, and is represented by its x and y coordinates each of which is written with six decimal places.
Finally, the third part is a list of (allowed) edges described by the its endpoints' indexes and its length. The length is presented rounded to six decimal places to avoid pitfalls and to facilitate comparisons. The list end is marked by the negative integer -1.
Any blank line or started by a '#' is considered as comments and is discarded. As an example, here is the representation of the vertices of a square with coordinates (10, 0) (0, 10) (-10, 0) and (0, -10):
| 4 | ||
| 0 | 10.000000 | 0.000000 |
| 1 | 0.000000 | 10.000000 |
| 2 | -10.000000 | 0.000000 |
| 3 | 0.000000 | -10.000000 |
| 0 | 1 | 14.142136 |
| 0 | 2 | 20.000000 |
| 0 | 3 | 14.142136 |
| 1 | 2 | 14.142136 |
| 1 | 3 | 20.000000 |
| 2 | 3 | 14.142136 |
| -1 |
Instances MDP2014a
Instances tested in the paper Computing Minimum Dilation Spanning Trees in Geometric Graphs by Aléx Brandt, Miguel Gaiowski, Pedro de Rezende, and Cid de Souza, 2014 (submitted).There is a total of 180 MDSTP instances, each one having between 10 and 20 points, all with the complete set of edges allowed:
- uniform distribution - instances[.tar.gz] (153kB)
References
- [1] Computing Minimum Dilation Spanning Trees in Geometric Graphs, Aléx Brandt, Miguel Gaiowski, Pedro de Rezende, and Cid de Souza, 2014 (submitted).
Address
Cid C. de Souza, and Pedro J. de RezendeUniversidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: