On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
From MaRDI portal
Publication:3954830
DOI10.1137/0211059zbMath0492.68050OpenAlexW2031671531MaRDI QIDQ3954830
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211059
Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)
Related Items (only showing first 100 items - show all)
Directional Geometric Routing on Mobile Ad Hoc Networks ⋮ Unnamed Item ⋮ Spanners in randomly weighted graphs: Euclidean case ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS ⋮ Light Euclidean Spanners with Steiner Points ⋮ An efficient algorithm for the three-dimensional diameter problem ⋮ Reachability problems for transmission graphs ⋮ The Stretch - Length Tradeoff in Geometric Networks: Average Case and Worst Case Study ⋮ Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Routing in Polygonal Domains ⋮ Improved bounds on the stretch factor of \(Y_{4}\) ⋮ Closest-pair queries and minimum-weight queries are equivalent for squares ⋮ An O(N log N) minimal spanning tree algorithm for N points in the plane ⋮ Computing relative neighbourhood graphs in the plane ⋮ An improved construction for spanners of disks ⋮ Efficient construction of a bounded-degree spanner with low weight ⋮ Kinetic \(k\)-semi-Yao graph and its applications ⋮ A simple algorithm for enumerating longest distances in the plane ⋮ Edge routing with ordered bundles ⋮ Selecting distances in the plane ⋮ Euclidean Steiner Spanners: Light and Sparse ⋮ Routing on heavy-path WSPD-spanners ⋮ Shortest paths in Euclidean graphs ⋮ On the symmetric angle-restricted nearest neighbor problem ⋮ Approximating geometric bottleneck shortest paths ⋮ (Weakly) self-approaching geometric graphs and spanners ⋮ Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors ⋮ The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric ⋮ On minimum and maximum spanning trees of linearly moving points ⋮ Distributed construction of low-interference spanners ⋮ Some problems in computational geometry ⋮ Routing among convex polygonal obstacles in the plane ⋮ An algorithm for generalized point location and its applications ⋮ APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS ⋮ COMPUTING THE DIAMETER OF A POINT SET ⋮ COMPUTING CLOSEST POINTS FOR SEGMENTS ⋮ Minimum power assignment in wireless ad hoc networks with spanner property ⋮ A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs ⋮ Truly Optimal Euclidean Spanners ⋮ Geometric spanners with applications in wireless networks ⋮ Algorithms for proximity problems in higher dimensions ⋮ Average case analysis of dynamic geometric optimization ⋮ Routing in polygonal domains ⋮ Approximating the diameter of a set of points in the Euclidean space ⋮ Spanning properties of Theta-Theta-6 ⋮ Spanners for Directed Transmission Graphs ⋮ Self-stabilizing spanner topology control solutions in wireless ad hoc networks ⋮ Fault tolerancy of continuous Yao graph of angle less than \(2\pi/5\) ⋮ On path-greedy geometric spanners ⋮ Relaxed spanners for directed disk graphs ⋮ Continuous Yao graphs ⋮ An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics ⋮ Spanners of Additively Weighted Point Sets ⋮ Cone-based spanners of constant degree ⋮ Spanners of additively weighted point sets ⋮ Improving upper and lower bounds for the total number of edge crossings of Euclidean minimum weight Laman graphs ⋮ On the angle restricted nearest neighbor problem ⋮ On certain geometric properties of the Yao-Yao graphs ⋮ Computing Euclidean maximum spanning trees ⋮ Emanation graph: a plane geometric spanner with Steiner points ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ The Euclidean bottleneck Steiner path problem and other applications of \((\alpha ,\beta )\)-pair decomposition ⋮ Locating battery charging stations to facilitate almost shortest paths ⋮ Sparse geometric graphs with small dilation ⋮ I/O-efficient algorithms for computing planar geometric spanners ⋮ Constructing the relative neighborhood graph in 3-dimensional Euclidean space ⋮ Euclidean minimum spanning trees and bichromatic closest pairs ⋮ A singly exponential stratification scheme for real semi-algebraic varieties and its applications ⋮ Local properties of geometric graphs ⋮ Minimizing interference of a wireless ad-hoc network in a plane ⋮ Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces ⋮ Classes of graphs which approximate the complete Euclidean graph ⋮ On the expected maximum degree of Gabriel and Yao graphs ⋮ Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points ⋮ Farthest neighbors, maximum spanning trees and related problems in higher dimensions ⋮ π/2-ANGLE YAO GRAPHS ARE SPANNERS ⋮ Approximating the generalized minimum Manhattan network problem ⋮ Transitions in geometric minimum spanning trees ⋮ Relative neighborhood graphs in three dimensions ⋮ Stable roommates spanner ⋮ Minimal containment under homothetics: a simple cutting plane approach ⋮ Ectropy of diversity measures for populations in Euclidean space ⋮ Conic nearest neighbor queries and approximate Voronoi diagrams ⋮ The \(\varTheta_5\)-graph is a spanner ⋮ On a family of strong geometric spanners that admit local routing strategies ⋮ Approximating nearest neighbor among triangles in convex position ⋮ Formal description and analysis of a distributed location service for mobile ad hoc networks ⋮ Sigma-local graphs ⋮ Improved local algorithms for spanner construction ⋮ Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces ⋮ The Orthant Neighborhood Graph: A Decentralized Spatial Data Structure for Dynamic Point Sets ⋮ Empty region graphs ⋮ Degree bounded bottleneck spanning trees in three dimensions ⋮ Practical methods for shape fitting and kinetic data structures using coresets ⋮ Local edge colouring of Yao-like subgraphs of unit disk graphs ⋮ Unnamed Item ⋮ A sparse graph almost as good as the complete graph on points in \(k\) dimensions
This page was built for publication: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
