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 graphsstretch factorminimum dilation

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

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

Cited in

(11)

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

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)