Approximating Layout Problems on Random Geometric Graphs
From MaRDI portal
Publication:2731603
DOI10.1006/jagm.2000.1149zbMath0974.68148OpenAlexW2019635018MaRDI QIDQ2731603
Mathew D. Penrose, Jordi Petit, Josep Diaz, Maria J. Serna
Publication date: 29 July 2001
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/81ecf8cb77f461719e8a69234dc41dc37be05b40
Related Items (25)
Consistency of modularity clustering on random geometric graphs ⋮ On Cutwidth Parameterized by Vertex Cover ⋮ Cutwidth of Split Graphs, Threshold Graphs, and Proper Interval Graphs ⋮ Variable neighborhood search for the vertex separation problem ⋮ Graph bandwidth of weighted caterpillars ⋮ Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs ⋮ Optimal Cheeger cuts and bisections of random geometric graphs ⋮ Minimum bisection is NP-hard on unit disk graphs ⋮ MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs ⋮ The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs ⋮ On a binary distance model for the minimum linear arrangement problem ⋮ On cutwidth parameterized by vertex cover ⋮ Large independent sets in general random intersection graphs ⋮ Optimal linear arrangements using betweenness variables ⋮ Hamilton cycles in random geometric graphs ⋮ Unnamed Item ⋮ Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time ⋮ Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem ⋮ Communication tree problems ⋮ Bipartite graphs of small readability ⋮ Layout of random circulant graphs ⋮ Experiments on the minimum linear arrangement problem ⋮ Balanced cut approximation in random geometric graphs ⋮ Expander properties and the cover time of random intersection graphs ⋮ Packing of (0, 1)-matrices
This page was built for publication: Approximating Layout Problems on Random Geometric Graphs
