Vertex ordering and partitioning problems for random spatial graphs.

DOI10.1214/aoap/1019487353zbMath1052.60080OpenAlexW2058010442MaRDI QIDQ1884828

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 optimizationrandom graphspercolation processes

Mathematics Subject Classification ID

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

Related Items (1)

Optimal Cheeger cuts and bisections of random geometric graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A framework for solving VLSI graph layout problems
• Black-white pebbles and graph separation
• Some simplified NP-complete graph problems
• Path optimization for graph partitioning problems
• Probability theory of classical Euclidean optimization problems
• Single linkage clustering and continuum percolation
• On the problem of reconstructing a tournament from subtournaments
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• On the Probable Performance of Heuristics for Bandwidth Minimization
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
• Probability with Martingales
• Nearest neighbor and hard sphere models in continuum percolation
• Optimal Numberings of an $N \times N$ Array
• COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗
• Large deviations for discrete and continuous percolation
• Optimal numberings and isoperimetric problems on graphs

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