Transitions in geometric minimum spanning trees
From MaRDI portal
Publication:1199130
DOI10.1007/BF02293049zbMATH Open0764.05022OpenAlexW2088839217MaRDI QIDQ1199130FDOQ1199130
Authors: 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
Recommendations
minimum spanning treecostEuclidean distancesensitivity measurelabelled treetopologically equivalent\(\varepsilon\)-perturbation
Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)
Cites Work
- Title not available (Why is that?)
- A data structure for dynamic trees
- A Fast Parametric Maximum Flow Algorithm and Applications
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- Fast Algorithms for Finding Nearest Common Ancestors
- Parametric Combinatorial Computing and a Problem of Program Module Distribution
- Some dynamic computational geometry problems
- Optimal attack and reinforcement of a network
- Selected Applications of Minimum Cuts in Networks
- On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
- A Cut Approach to the Rectilinear Distance Facility Location Problem
- Computing Euclidean maximum spanning trees
- The 1-steiner tree problem
- Parametric stable marriage and minimum cuts
- New upper bounds for neighbor searching
Cited In (51)
- Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem
- On the Topologies of Local Minimum Spanning Trees
- Polynomial area bounds for MST embeddings of trees
- A 4-approximation of the \(\frac{2\pi }{3} \)-MST
- The minimum moving spanning tree problem
- Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric
- Drawing a rooted tree as a rooted \(y\)-monotone minimum spanning tree
- PROXIMITY DRAWINGS OF HIGH-DEGREE TREES
- Degree-bounded minimum spanning trees
- Relay placement for fault tolerance in wireless networks in higher dimensions
- Succinct greedy drawings do not always exist
- Cut locus realizations on convex polyhedra
- Drawing a tree as a minimum spanning tree approximation
- Polynomial Area Bounds for MST Embeddings of Trees
- Proximity drawings in polynomial area and volume
- The Minimum Moving Spanning Tree Problem
- Cooperative TSP
- On the restricted 1-Steiner tree problem
- On the restricted \(k\)-Steiner tree problem
- Improved algorithms in directional wireless sensor networks
- Characterizing proximity trees
- The realization problem for Euclidean minimum spanning trees is NP-hard
- Algorithms for Euclidean Degree Bounded Spanning Tree Problems
- Bounded-angle minimum spanning trees
- A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees
- Low-degree minimum spanning trees
- DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
- On nearest-neighbor graphs
- Drawing graphs as spanners
- Title not available (Why is that?)
- Voronoi drawings of trees
- Using Lagrangian dual information to generate degree constrained spanning trees
- md-MST is NP-hard for \(d\geq 3\)
- Degree-bounded minimum spanning tree for unit disk graph
- Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations
- Approximating the bottleneck plane perfect matching of a point set
- Generalised \(k\)-Steiner tree problems in normed planes
- On the number of minimal 1-Steiner trees
- Euclidean bottleneck bounded-degree spanning tree ratios
- Structural tolerance and Delaunay triangulation
- On minimum and maximum spanning trees of linearly moving points
- On improved bounds for bounded degree spanning trees for points in arbitrary dimension
- Approximation algorithms for solving the line-capacitated minimum Steiner tree problem
- Degree bounded bottleneck spanning trees in three dimensions
- Witness (Delaunay) graphs
- The drawability problem for minimum weight triangulations
- Strong matching of points with geometric shapes
- IMPROVING SHORTEST PATHS IN THE DELAUNAY TRIANGULATION
- A 4-approximation of the \(\frac{ 2 \pi}{ 3} \)-MST
- PROXIMITY GRAPHS: E, δ, Δ, χ AND ω
- On the area requirements of Euclidean minimum spanning trees
This page was built for publication: Transitions in geometric minimum spanning trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1199130)
