Vertex ordering and partitioning problems for random spatial graphs.

DOI10.1214/AOAP/1019487353MaRDI QIDQ1884828zbMATH OpenOpenAlexFDO

Authors Mathew D. Penrose

Publication date 27 October 2004

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1214/aoap/1019487353

zbMATH Keywords

combinatorial optimizationpercolation processesrandom graphs

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Review text

For a finite graph of order \(n\) the vertices are labeled by integers \(1,\dots,n\) and any edge between \(i\) and \(j\) is given the weight \(i-j\) for \(i\) larger than \(j\). The labeling has to be chosen so that some functional of the edge weights is minimized. Such optimization problems are considered for various functionals when the vertices correspond to points randomly distributed on the \(d\)-dimensional unit cube, and the points are adjacent when they are at most a fixed threshold apart.

Recommendations

• scientific article; zbMATH DE number 3855167
• Optimal vertex ordering of graphs
• Optimal Numberings of an N \times N Array
• scientific article; zbMATH DE number 4047762

Cites work

• A framework for solving VLSI graph layout problems
• Black-white pebbles and graph separation
• COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗
• scientific article; zbMATH DE number 437546 (Why is no real title available?)
• scientific article; zbMATH DE number 3630808 (Why is no real title available?)
• scientific article; zbMATH DE number 1303559 (Why is no real title available?)
• scientific article; zbMATH DE number 828046 (Why is no real title available?)
• scientific article; zbMATH DE number 863492 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• scientific article; zbMATH DE number 3193293 (Why is no real title available?)
• Large deviations for discrete and continuous percolation
• Nearest neighbor and hard sphere models in continuum percolation
• On the Probable Performance of Heuristics for Bandwidth Minimization
• On the problem of reconstructing a tournament from subtournaments
• Optimal numberings and isoperimetric problems on graphs
• Optimal Numberings of an N \times N Array
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• Path optimization for graph partitioning problems
• Percolation. With 76 illustrations
• Probability theory of classical Euclidean optimization problems
• Probability with Martingales
• Single linkage clustering and continuum percolation
• Some simplified NP-complete graph problems
• The MINSUMCUT problem
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees

Cited in

(2)

• Optimal Cheeger cuts and bisections of random geometric graphs
• Optimal Numberings of an N \times N Array

This page was built for publication: Vertex ordering and partitioning problems for random spatial graphs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1884828)