Computing Minimum Dilation Spanning Trees in Geometric Graphs

DOI10.1007/978-3-319-21398-9_24zbMath1465.68266OpenAlexW2276605036MaRDI QIDQ3196394

Pedro J. de Rezende, Miguel F. A.de M. Gaiowski, Aléx F. Brandt, 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)

Related Items (1)

General variable neighborhood search for the minimum stretch spanning tree problem

Cites Work

• Unnamed Item
• Sparse geometric graphs with small dilation
• Computing a minimum-dilation spanning tree is NP-hard
• GRASP and path relinking for the max-min diversity problem
• Geometric Spanner Networks
• Computing Geometric Minimum-Dilation Graphs Is NP-Hard
• Graph spanners
• Experimental study of geometric t -spanners
• Algorithms – ESA 2004

This page was built for publication: Computing Minimum Dilation Spanning Trees in Geometric Graphs