Computing a minimum-dilation spanning tree is NP-hard
type: Item
instance of: scholarly article
title: Computing a minimum-dilation spanning tree is NP-hard
zbMATH Open document ID: 1188.65018
published in: Computational Geometry
publication date: 2008-09-19T00:00:00Z
Mathematics Subject Classification ID: 65D18
zbMATH DE Number: 5345382
zbMATH Keywords: spanner
zbMATH Keywords: dilation
zbMATH Keywords: optimization
zbMATH Keywords: spanning tree
zbMATH Keywords: geometric network
zbMATH Keywords: NP-hardness
zbMATH Keywords: shortest path
author: Otfried Cheong
author: Herman Haverkort
author: Mira Lee
MaRDI profile type: Publication
full work available at URL: j.comgeo.2007.12.001
OpenAlex ID: W2065889331
cites work: Sparse geometric graphs with small dilation
cites work: CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
cites work: Q4945509
cites work: Algorithms – ESA 2005
cites work: Tree spanners in planar graphs
cites work: Computing Geometric Minimum-Dilation Graphs Is NP-Hard
cites work: There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
cites work: CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
cites work: Q4945521
cites work: A sparse graph almost as good as the complete graph on points in \(k\) dimensions
DOI: 10.1016/J.COMGEO.2007.12.001
description: scientific article; zbMATH DE number 5345382