Computing minimum dilation spanning trees in geometric graphs

DOI10.1007/978-3-319-21398-9_24MaRDI QIDQ3196394zbMATH OpenOpenAlexFDO

Authors Aléx F. Brandt, Miguel F. A.de M. Gaiowski, Pedro J. de Rezende, Cid Carvalho de Souza

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21398-9_24

zbMATH Keywords

geometric graphsminimum dilationstretch factor

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Computing a minimum-dilation spanning tree is NP-hard
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• Minimum dilation stars
• Computing a (1+)-approximate geometric minimum-diameter spanning tree
• SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES

Cites work

• Algorithms – ESA 2004
• Computing a minimum-dilation spanning tree is NP-hard
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• Experimental study of geometric \(t\)-spanners
• Geometric Spanner Networks
• Graph spanners
• GRASP and path relinking for the max-min diversity problem
• scientific article; zbMATH DE number 2050708 (Why is no real title available?)
• Sparse geometric graphs with small dilation

Cited in

(12)

• An exact algorithm for the minimum dilation triangulation problem
• SINGLE-SOURCE DILATION-BOUNDED MINIMUM SPANNING TREES
• Computing geometric minimum-dilation graphs is NP-hard
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• scientific article; zbMATH DE number 5542484 (Why is no real title available?)
• Minimum dilation stars
• Algorithms and Computation
• Algorithms and Computation
• General variable neighborhood search for the minimum stretch spanning tree problem
• Optimal spanners for axis-aligned rectangles
• Bicriteria approximation for minimum dilation graph augmentation
• Computing a minimum-dilation spanning tree is NP-hard

This page was built for publication: Computing minimum dilation spanning trees in geometric graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196394)