Approximating the Stretch Factor of Euclidean Graphs
From MaRDI portal
Publication:4507380
DOI10.1137/S0097539799361671zbMath0966.68205OpenAlexW2076014803MaRDI QIDQ4507380
Giri Narasimhan, Michiel H. M. 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
Related Items (22)
Algorithms for graphs of bounded treewidth via orthogonal range searching ⋮ On the dilation spectrum of paths, cycles, and trees ⋮ Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs ⋮ Connect the Dot: Computing Feed-Links with Minimum Dilation ⋮ DILATION-OPTIMAL EDGE DELETION IN POLYGONAL CYCLES ⋮ Minimum dilation stars ⋮ Spanners in randomly weighted graphs: Euclidean case ⋮ Almost all Delaunay triangulations have stretch factor greater than \(\pi /2\) ⋮ A fast algorithm for approximating the detour of a polygonal chain. ⋮ Dilation-Optimal Edge Deletion in Polygonal Cycles ⋮ Linear time algorithm for optimal feed-link placement ⋮ Testing Euclidean Spanners ⋮ COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE ⋮ Distribution-sensitive construction of the greedy spanner ⋮ Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D ⋮ 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 ⋮ Thresholding random geometric graph properties motivated by ad hoc sensor networks ⋮ Unnamed Item ⋮ Deformable spanners and applications ⋮ Many distances in planar graphs ⋮ On the Stretch Factor of Polygonal Chains
This page was built for publication: Approximating the Stretch Factor of Euclidean Graphs
