NP-completeness of minimum spanner problems
From MaRDI portal
Publication:1315465
DOI10.1016/0166-218X(94)90073-6zbMath0788.68057MaRDI QIDQ1315465
Publication date: 10 March 1994
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (22)
Graph spanners in the streaming model: An experimental study ⋮ Small stretch \((\alpha ,\beta )\)-spanners in the streaming model ⋮ Light graphs with small routing cost ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Parameterized complexity of directed spanner problems ⋮ Restrictions of minimum spanner problems ⋮ A PTAS for the sparsest 2-spanner of 4-connected planar triangulations ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Spanners and message distribution in networks. ⋮ COMPUTING GEOMETRIC MINIMUM-DILATION GRAPHS IS NP-HARD ⋮ Combinatorial network abstraction by trees and distances ⋮ Parameterized Complexity of Directed Spanner Problems. ⋮ A linear time algorithm to construct a tree 4-spanner on trapezoid graphs ⋮ An optimal parallel algorithm to construct a tree 3-spanner on interval graphs ⋮ Tree spanners in planar graphs ⋮ Max-stretch reduction for tree spanners ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ Graph spanners: a tutorial review ⋮ NP-hardness and fixed-parameter tractability of the minimum spanner problem ⋮ ON SPANNERS OF GEOMETRIC GRAPHS ⋮ Sparsification lower bound for linear spanners in directed graphs ⋮ Edge-disjoint spanners of complete graphs and complete digraphs
Cites Work
This page was built for publication: NP-completeness of minimum spanner problems
