NP-hardness and fixed-parameter tractability of the minimum spanner problem
DOI10.1016/J.TCS.2018.06.031zbMATH Open1401.68098OpenAlexW2810702411MaRDI QIDQ1784745FDOQ1784745
Authors: Yusuke Kobayashi 
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Graph theory
- Title not available (Why is that?)
- Approximate distance oracles
- Computing almost shortest paths
- An Optimal Synchronizer for the Hypercube
- Tree Spanners
- Graph spanners
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Spanners in graphs of bounded degree
- New additive spanners
- A trade-off between space and efficiency for routing tables
- Polylog-time and near-linear work approximation scheme for undirected shortest paths
- Tree 3-spanners on interval, permutation and regular bipartite graphs
- NP-completeness of minimum spanner problems
- Restrictions of minimum spanner problems
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
- The 4/3 additive spanner exponent is tight
- Title not available (Why is that?)
- Compact roundtrip routing in directed networks
- Near-optimal light spanners
Cited In (18)
- Graph spanners: a tutorial review
- Title not available (Why is that?)
- Parameterized Complexity of Directed Spanner Problems.
- A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
- Title not available (Why is that?)
- An FPT Algorithm for Minimum Additive Spanner Problem.
- NP-completeness of minimum spanner problems
- On Spanners of Geometric Graphs
- Complexity of the multiobjective minimum weight minimum stretch spanner problem
- Minimum \(t\)-spanners on subcubic graphs
- Parameterized complexity of directed spanner problems
- Polynomial algorithms for sparse spanners on subcubic graphs
- Approximation of minimum weight spanners for sparse graphs
- Sparsification lower bound for linear spanners in directed graphs
- A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
- The minimum spanning strong subdigraph problem is fixed parameter tractable
- Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
- Title not available (Why is that?)
This page was built for publication: NP-hardness and fixed-parameter tractability of the minimum spanner problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1784745)
