Given an ordering of the vertices of a finite graph, let the induced
weight for an edge be the separation of its endpoints in the ordering. Layout
problems involve choosing the ordering to minimize a cost functional such as
the sum or maximum of the edge weights. We give growth rates for the costs of
some of these problems on supercritical percolation processes and supercritical
random geometric graphs, obtained by placing vertices randomly in the unit cube
and joining them whenever at most some threshold distance apart.
Publié le : 2000-05-14
Classification:
Combinatorial optimization,
percolation,
random graphs,
connectivity,
geometric probability,
large deviations.,
05C78,
60D05,
05C80,
60K35
@article{1019487353,
author = {Penrose, Mathew D.},
title = {Vertex ordering and partitioning problems for random spatial
graphs},
journal = {Ann. Appl. Probab.},
volume = {10},
number = {2},
year = {2000},
pages = { 517-538},
language = {en},
url = {http://dml.mathdoc.fr/item/1019487353}
}
Penrose, Mathew D. Vertex ordering and partitioning problems for random spatial
graphs. Ann. Appl. Probab., Tome 10 (2000) no. 2, pp. 517-538. http://gdmltest.u-ga.fr/item/1019487353/