NP-hardness and fixed-parameter tractability of the minimum spanner problem
From MaRDI portal
Publication:1784745
DOI10.1016/j.tcs.2018.06.031zbMath1401.68098OpenAlexW2810702411MaRDI QIDQ1784745
Publication date: 27 September 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/244837
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (6)
Minimum \(t\)-spanners on subcubic graphs ⋮ Parameterized complexity of directed spanner problems ⋮ Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs ⋮ Parameterized Complexity of Directed Spanner Problems. ⋮ Graph spanners: a tutorial review ⋮ Sparsification lower bound for linear spanners in directed graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tree 3-spanners on interval, permutation and regular bipartite graphs
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
- NP-completeness of minimum spanner problems
- Restrictions of minimum spanner problems
- Approximate distance oracles
- Graph spanners
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Spanners in graphs of bounded degree
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Near-Optimal Light Spanners
- The 4/3 Additive Spanner Exponent Is Tight
- A trade-off between space and efficiency for routing tables
- An Optimal Synchronizer for the Hypercube
- Compact roundtrip routing in directed networks
- Tree Spanners
- New Additive Spanners
- Computing almost shortest paths
This page was built for publication: NP-hardness and fixed-parameter tractability of the minimum spanner problem
