Computing a minimum-dilation spanning tree is NP-hard (Q945943): Difference between revisions

@@ Property / author @@
-Otfried Schwarzkopf
@@ Property / author: Otfried Schwarzkopf / rank @@
-Normal rank
@@ Property / author @@
-Herman J. Haverkort
@@ Property / author: Herman J. Haverkort / rank @@
-Normal rank
@@ Property / author @@
-Mi Ra Lee
@@ Property / author: Mi Ra Lee / rank @@
-Normal rank
@@ Property / author @@
+Otfried Schwarzkopf
@@ Property / author: Otfried Schwarzkopf / rank @@
+Normal rank
@@ Property / author @@
+Herman J. Haverkort
@@ Property / author: Herman J. Haverkort / rank @@
+Normal rank
@@ Property / author @@
+Mi Ra Lee
@@ Property / author: Mi Ra Lee / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.comgeo.2007.12.001
+Normal rank
@@ Property / OpenAlex ID @@
+W2065889331
@@ Property / OpenAlex ID: W2065889331 / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse geometric graphs with small dilation
@@ Property / cites work: Sparse geometric graphs with small dilation / rank @@
+Normal rank
@@ Property / cites work @@
+CONSTRUCTING DEGREE-3 SPANNERS WITH OTHER SPARSENESS PROPERTIES
+Normal rank
@@ Property / cites work @@
+Q4945509
@@ Property / cites work: Q4945509 / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithms – ESA 2005
@@ Property / cites work: Algorithms – ESA 2005 / rank @@
+Normal rank
@@ Property / cites work @@
+Tree spanners in planar graphs
@@ Property / cites work: Tree spanners in planar graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Computing Geometric Minimum-Dilation Graphs Is NP-Hard
+Normal rank
@@ Property / cites work @@
+There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees
+Normal rank
@@ Property / cites work @@
+CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS
@@ Property / cites work: CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS / rank @@
+Normal rank
@@ Property / cites work @@
+Q4945521
@@ Property / cites work: Q4945521 / rank @@
+Normal rank
@@ Property / cites work @@
+A sparse graph almost as good as the complete graph on points in \(k\) dimensions
+Normal rank