Fitting Voronoi diagrams to planar tesselations
- Authors: Aloupis, Greg , Pérez-Rosés, Hebert , Pineda-Villavicencio, Guillermo , Taslakian, Perouz , Trinchet-Almaguer, Dannier
- Date: 2013
- Type: Text , Conference paper
- Relation: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Vol. 8288 LNCS, p. 349-361
- Full Text:
- Reviewed:
- Description: Given a tesselation of the plane, defined by a planar straight-line graph G, we want to find a minimal set S of points in the plane, such that the Voronoi diagram associated with S 'fits' G. This is the Generalized Inverse Voronoi Problem (GIVP), defined in [12] and rediscovered recently in [3]. Here we give an algorithm that solves this problem with a number of points that is linear in the size of G, assuming that the smallest angle in G is constant. © 2013 Springer-Verlag.
The maximum degree & diameter-bounded subgraph and its applications
- Authors: Dekker, Anthony , Pérez-Rosés, Hebert , Pineda-Villavicencio, Guillermo , Watters, Paul
- Date: 2012
- Type: Text , Journal article
- Relation: Journal of Mathematical Modelling and Algorithms Vol. 11, no. 3 (2012), p. 249-268
- Full Text: false
- Reviewed:
- Description: We introduce the problem of finding the largest subgraph of a given weighted undirected graph (host graph), subject to constraints on the maximum degree and the diameter. We discuss some applications in security, network design and parallel processing, and in connection with the latter we derive some bounds for the order of the largest subgraph in host graphs of practical interest: the mesh and the hypercube. We also present a heuristic strategy to solve the problem, and we prove an approximation ratio for the algorithm. Finally, we provide some experimental results with a variety of host networks, which show that the algorithm performs better in practice than the prediction provided by our theoretical approximation ratio.
New largest known graphs of diameter 6
- Authors: Pineda-Villavicencio, Guillermo , Gómez, José , Miller, Mirka , Pérez-Rosés, Hebert
- Date: 2009
- Type: Text , Journal article
- Relation: Networks Vol. 53, no. 4 (2009), p. 315-328
- Full Text:
- Reviewed:
- Description: In the pursuit of obtaining largest graphs of given maximum degree
- Description: 2003007890
New largest graphs of diameter 6. (Extended Abstract)
- Authors: Pineda-Villavicencio, Guillermo , Gomez, Jose , Miller, Mirka , Pérez-Rosés, Hebert
- Date: 2006
- Type: Text , Journal article
- Relation: Electronic Notes in Discrete Mathematics Vol. 24, no. (2006), p. 153-160
- Full Text:
- Reviewed:
- Description: In the pursuit of obtaining largest graphs of given degree and diameter, many construction techniques have arisen. Compounding of graphs is one such technique. In this paper, by means of the compounding of complete graphs into the bipartite Moore graph of diameter 6, we obtain two families of (
- Description: C1