Separators for sphere-packings and nearest neighbor graphs
From MaRDI portal
Publication:4371696
DOI10.1145/256292.256294zbMath0883.68100OpenAlexW2068019092WikidataQ29040016 ScholiaQ29040016MaRDI QIDQ4371696
William P. Thurston, Shang-Hua Teng, Gary Lee Miller, Stephen A. Vavasis
Publication date: 22 January 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1997-44/
Related Items
Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond, Scribability problems for polytopes, On the complexity of barrier resilience for fat regions and bounded ply, Simple polytopes without small separators. II: Thurston's bound, On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Apollonian ball packings and stacked polytopes, k-Centerpoints Conjectures for Pointsets in ℝd, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Spectral partitioning works: planar graphs and finite element meshes, Space saving by dynamic algebraization based on tree-depth, Simple polytopes without small separators, Small strong epsilon nets, Computing list homomorphisms in geometric intersection graphs, Maximum matchings in geometric intersection graphs, A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite‐element matrices, On weighted sublinear separators, Clique-based separators for geometric intersection graphs, Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane, Non-existence of annular separators in geometric graphs, New constructions of SSPDs and their applications, Unnamed Item, Contact graphs of ball packings, Network Essence: PageRank Completion and Centrality-Conforming Markov Chains, Unnamed Item, PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs, Discussion about properties of first nearest neighbor graphs, Unnamed Item, An optimal extension of the centerpoint theorem, Vulnerability of nearest neighbor graphs, On strong centerpoints, Separator theorems and Turán-type results for planar intersection graphs, Ramsey numbers of cubes versus cliques, Minimum vertex cover in ball graphs through local search, Poincaré profiles of groups and spaces, Geometric Separators for Finite-Element Meshes, Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation, Min-max-boundary domain decomposition, Conical equipartitions of mass distributions, COMPACT REPRESENTATIONS OF SIMPLICIAL MESHES IN TWO AND THREE DIMENSIONS, Centerpoints and Tverberg's technique, Computing the center region and its variants, A Separator Theorem for String Graphs and its Applications, A Separator Theorem for String Graphs and Its Applications, Unimodular hyperbolic triangulations: circle packing and random walk, Domination in Geometric Intersection Graphs, Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces, Balanced line separators of unit disk graphs, Unnamed Item, Unnamed Item, Subexponential algorithms for variants of the homomorphism problem in string graphs, A Glimpse into Thurston’s Work, Inference for Misspecified Models With Fixed Regressors, Notes on graph product structure theory, Edge integrity of nearest neighbor graphs and separator theorems, Minimizing Co-location Potential of Moving Entities, Parallel Algorithms for Nearest Neighbor Search Problems in High Dimensions, Six Topics on Inscribable Polytopes, Separators in region intersection graphs, Sublinear Separators in Intersection Graphs of Convex Shapes, Upper eigenvalue bounds for the Kirchhoff Laplacian on embedded metric graphs, Unnamed Item, Distance geometry for kissing spheres, A tight analysis of geometric local search
Uses Software
