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
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, On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces, The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension, An algorithm for geometric minimum spanning trees requiring nearly linear expected time, Asymptotics of geometrical navigation on a random set of points in the plane, Geometric spanner games, \(1\)-line minimum rectilinear Steiner trees and related problems, Closest-pair queries in fat rectangles, Odd Yao-Yao Graphs are Not Spanners, Efficient minimum spanning tree construction with Delaynay triangulation, On computing all north-east nearest neighbors in the \(L_ 1\) metric, On computing the diameter of a point set in high dimensional Euclidean space., A simple, faster method for kinetic proximity problems, Fast approximations for sums of distances, clustering and the Fermat-Weber problem, 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
