scientific article; zbMATH DE number 1424297

Publication date: 24 September 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

planar graphs spanners spanning trees network design problems

Trees (05C05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Beta-skeletons have unbounded dilation ⋮ Sparse hop spanners for unit disk graphs ⋮ Computing a \((1+\varepsilon)\)-approximate geometric minimum-diameter spanning tree ⋮ An improved construction for spanners of disks ⋮ On the spanning and routing ratios of the directed \(\varTheta_6\)-graph ⋮ On the dilation spectrum of paths, cycles, and trees ⋮ On stars and Steiner stars ⋮ Approximating geometric bottleneck shortest paths ⋮ Distributed construction of low-interference spanners ⋮ On the spanning and routing ratios of the directed \(\Theta_6\)-graph ⋮ Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs ⋮ Optimal Embedding into Star Metrics ⋮ Geometric spanners with applications in wireless networks ⋮ Improved upper bounds for the Steiner ratio ⋮ On the geometric dilation of closed curves, graphs, and point sets ⋮ Minimum dilation stars ⋮ Long non-crossing configurations in the plane ⋮ Spanning properties of Theta-Theta-6 ⋮ Geometric dilation of closed planar curves: New lower bounds ⋮ An exact algorithm for the minimum dilation triangulation problem ⋮ Vertex Fault-Tolerant Geometric Spanners for Weighted Points ⋮ Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm ⋮ On bounded leg shortest paths problems ⋮ Near-linear-time deterministic plane Steiner spanners for well-spaced point sets ⋮ The minimum Manhattan network problem: Approximations and exact solutions ⋮ The minimum-area spanning tree problem ⋮ On the power of the semi-separated pair decomposition ⋮ Upper bounds for minimum dilation triangulation in two special cases ⋮ Plane hop spanners for unit disk graphs: simpler and better ⋮ Unnamed Item ⋮ Computing the greedy spanner in near-quadratic time ⋮ The saga of minimum spanning trees ⋮ A fast algorithm for approximating the detour of a polygonal chain. ⋮ Sparse geometric graphs with small dilation ⋮ I/O-efficient algorithms for computing planar geometric spanners ⋮ Computing a minimum-dilation spanning tree is NP-hard ⋮ Angle-constrained spanners with angle at least \(\pi/3\) ⋮ A rounding algorithm for approximating minimum Manhattan networks ⋮ A simple and efficient kinetic spanner ⋮ Most finite point sets in the plane have dilation \(>1\) ⋮ Kinetic spanners in \(\mathbb R^{d}\) ⋮ Minimum weight convex Steiner partitions ⋮ A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation ⋮ Optimal spanners for axis-aligned rectangles ⋮ A near linear time approximation scheme for Steiner tree among obstacles in the plane ⋮ The folk solution and Boruvka's algorithm in minimum cost spanning tree problems ⋮ Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies ⋮ Unnamed Item ⋮ Deformable spanners and applications ⋮ Lattice Spanners of Low Degree ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Lower Bounds on the Dilation of Plane Spanners ⋮ Vertex fault-tolerant spanners for weighted points in polygonal domains ⋮ Light orthogonal networks with constant geometric dilation ⋮ Region-fault tolerant geometric spanners ⋮ Many distances in planar graphs ⋮ On the shortest separating cycle ⋮ Lattice spanners of low degree ⋮ Computing the dilation of edge-augmented graphs in metric spaces ⋮ On the longest spanning tree with neighborhoods ⋮ An improved upper bound on dilation of regular polygons ⋮ On the Stretch Factor of Polygonal Chains ⋮ Odd Yao-Yao Graphs are Not Spanners ⋮ Average stretch factor: how low does it go?