Transitions in geometric minimum spanning trees

DOI10.1007/BF02293049zbMath0764.05022OpenAlexW2088839217MaRDI QIDQ1199130

Subhash Suri, Clyde l. Monma

Publication date: 16 January 1993

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02293049

zbMATH Keywords

costminimum spanning treeEuclidean distancesensitivity measurelabelled treetopologically equivalent\(\varepsilon\)-perturbation

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)

Related Items

md-MST is NP-hard for ⋮ On the number of minimal 1-Steiner trees ⋮ The Minimum Moving Spanning Tree Problem ⋮ Proximity drawings in polynomial area and volume ⋮ The minimum moving spanning tree problem ⋮ A 4-approximation of the \(\frac{2\pi }{3} \)-MST ⋮ Succinct greedy drawings do not always exist ⋮ PROXIMITY GRAPHS: E, δ, Δ, χ AND ω ⋮ IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION ⋮ Low-degree minimum spanning trees ⋮ PROXIMITY DRAWINGS OF HIGH-DEGREE TREES ⋮ On nearest-neighbor graphs ⋮ Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations ⋮ Unnamed Item ⋮ The realization problem for Euclidean minimum spanning trees is NP-hard ⋮ Characterizing proximity trees ⋮ On the area requirements of Euclidean minimum spanning trees ⋮ Improved algorithms in directional wireless sensor networks ⋮ Cut locus realizations on convex polyhedra ⋮ Drawing a tree as a minimum spanning tree approximation ⋮ Strong matching of points with geometric shapes ⋮ Approximating the bottleneck plane perfect matching of a point set ⋮ Relay placement for fault tolerance in wireless networks in higher dimensions ⋮ Polynomial area bounds for MST embeddings of trees ⋮ Drawing a rooted tree as a rooted \(y\)-monotone minimum spanning tree ⋮ A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees ⋮ On improved bounds for bounded degree spanning trees for points in arbitrary dimension ⋮ Generalised \(k\)-Steiner tree problems in normed planes ⋮ Using Lagrangian dual information to generate degree constrained spanning trees ⋮ Witness (Delaunay) graphs ⋮ On the restricted 1-Steiner tree problem ⋮ Cooperative TSP ⋮ DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH ⋮ Algorithms for Euclidean Degree Bounded Spanning Tree Problems ⋮ The drawability problem for minimum weight triangulations ⋮ Polynomial Area Bounds for MST Embeddings of Trees ⋮ Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ Drawing graphs as spanners ⋮ Degree-bounded minimum spanning trees ⋮ Euclidean bottleneck bounded-degree spanning tree ratios ⋮ Degree-bounded minimum spanning tree for unit disk graph ⋮ Bounded-angle minimum spanning trees ⋮ On the restricted \(k\)-Steiner tree problem ⋮ A 4-approximation of the \(\frac{ 2 \pi}{ 3} \)-MST ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem ⋮ Structural tolerance and Delaunay triangulation ⋮ Voronoi drawings of trees

Cites Work

• Unnamed Item
• Computing Euclidean maximum spanning trees
• Parametric stable marriage and minimum cuts
• Some dynamic computational geometry problems
• A data structure for dynamic trees
• Fast Algorithms for Finding Nearest Common Ancestors
• New upper bounds for neighbor searching
• Parametric Combinatorial Computing and a Problem of Program Module Distribution
• Optimal attack and reinforcement of a network
• The 1-steiner tree problem
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Selected Applications of Minimum Cuts in Networks
• A Cut Approach to the Rectilinear Distance Facility Location Problem
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• A Fast Parametric Maximum Flow Algorithm and Applications