Loading...
Loading...

Go to the content (press return)

Linear orderings of random geometric graphs (extended abstract)

Author
Diaz, J.; Penrose, M.; Petit, J.; Serna, M.
Type of activity
Report
Date
1999-04
Code
R99-11
Repository
http://hdl.handle.net/2117/93009 Open in new window
Abstract
In random geometric graphs, vertices are randomly distributed on [0,1]^2 and pairs of vertices are connected by edges whenever they are sufficiently close together. Layout problems seek a linear ordering of the vertices of a graph such that a certain measure is minimized. In this paper, we study several layout problems on random geometric graphs: Bandwidth, Minimum Linear Arrangement, Minimum Cut, Minimum Sum Cut, Vertex Separation and Bisection. We first prove that some of these problems remain...
Citation
Diaz, J., Penrose, M., Petit, J., Serna, M. "Linear orderings of random geometric graphs (extended abstract)". 1999.
Keywords
Random geometric graphs, layout problems
Group of research
ALBCOM - Algorithms, Computational Biology, Complexity and Formal Methods

Participants

Attachments