Approximating the Stretch Factor of Euclidean Graphs
From MaRDI portal
Publication:4507380
DOI10.1137/S0097539799361671zbMATH Open0966.68205OpenAlexW2076014803MaRDI QIDQ4507380FDOQ4507380
Authors: Giri Narasimhan, Michiel Smid 
Publication date: 18 October 2000
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539799361671
Recommendations
- Approximating the average stretch factor of geometric graphs
- Approximating the average stretch factor of geometric graphs
- On the stretch factor of convex Delaunay graphs
- On the Stretch Factor of Convex Delaunay Graphs
- scientific article; zbMATH DE number 4070353
- Computing the stretch of an embedded graph
- Stretch and diameter in random geometric graphs
- On the stretch factor of randomly embedded random graphs
- Towards tight approximation bounds for graph diameter and eccentricities
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
Cited In (28)
- Approximating the average stretch factor of geometric graphs
- Dilation-Optimal Edge Deletion in Polygonal Cycles
- Minimum dilation stars
- On the dilation spectrum of paths, cycles, and trees
- Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D
- Many distances in planar graphs
- Bounded-degree plane geometric spanners in practice
- Approximating the average stretch factor of geometric graphs
- Thresholding random geometric graph properties motivated by ad hoc sensor networks
- Dilation-optimal edge deletion in polygonal cycles
- Title not available (Why is that?)
- Spanners in randomly weighted graphs: Euclidean case
- Improving the Stretch Factor of a Geometric Network by Edge Augmentation
- Title not available (Why is that?)
- Testing Euclidean Spanners
- Computing the stretch factor and maximum detour of paths, trees, and cycles in the normed space
- Linear time algorithm for optimal feed-link placement
- Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs
- On the stretch factor of polygonal chains
- Connect the Dot: Computing Feed-Links with Minimum Dilation
- Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\)
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- A fast algorithm for approximating the detour of a polygonal chain.
- Deformable spanners and applications
- Title not available (Why is that?)
- A PTAS for minimum vertex dilation triangulation of a simple polygon with a constant number of sources of dilation
- Local construction and coloring of spanners of location aware unit disk graphs
- Distribution-sensitive construction of the greedy spanner
This page was built for publication: Approximating the Stretch Factor of Euclidean Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4507380)
