Vertex ordering and partitioning problems for random spatial graphs.
type: Item
instance of: scholarly article
title: Vertex ordering and partitioning problems for random spatial graphs.
zbMATH Open document ID: 1052.60080
author: Mathew D. Penrose
published in: The Annals of Applied Probability
publication date: 2004-10-27T00:00:00Z
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.
Mathematics Subject Classification ID: 60K35
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 2110913
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: random graphs
zbMATH Keywords: percolation processes
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1214/aoap/1019487353
OpenAlex ID: W2058010442
cites work: Q5729634
cites work: Path optimization for graph partitioning problems
cites work: A framework for solving VLSI graph layout problems
cites work: Q4871771
cites work: Q4037408
cites work: Q4859012
cites work: COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗
cites work: Some simplified NP-complete graph problems
cites work: Q4693063
cites work: On the problem of reconstructing a tournament from subtournaments
cites work: Optimal numberings and isoperimetric problems on graphs
cites work: Q4192107
cites work: Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
cites work: Q3140423
cites work: Black-white pebbles and graph separation
cites work: Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees
cites work: Nearest neighbor and hard sphere models in continuum percolation
cites work: Optimal Numberings of an $N \times N$ Array
cites work: Single linkage clustering and continuum percolation
cites work: Large deviations for discrete and continuous percolation
cites work: Q4250184
cites work: Q5691080
cites work: On the Probable Performance of Heuristics for Bandwidth Minimization
cites work: Probability with Martingales
cites work: Probability theory of classical Euclidean optimization problems
DOI: 10.1214/AOAP/1019487353
description: scientific article; zbMATH DE number 2110913