NP-hardness and fixed-parameter tractability of the minimum spanner problem

DOI10.1016/J.TCS.2018.06.031MaRDI QIDQ1784745zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

FPT algorithmNP-hardnessplanar graphsdegree-bounded graphsminimum spanner problem

Mathematics Subject Classification ID

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)

Recommendations

• Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
• scientific article; zbMATH DE number 1375574
• scientific article; zbMATH DE number 1107724
• Tree spanners in planar graphs
• NP-completeness of minimum spanner problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1107724 (Why is no real title available?)
• A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
• A trade-off between space and efficiency for routing tables
• An Optimal Synchronizer for the Hypercube
• Approximate distance oracles
• Compact roundtrip routing in directed networks
• Computing almost shortest paths
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Graph spanners
• Graph theory
• NP-completeness of minimum spanner problems
• Near-optimal light spanners
• New additive spanners
• Polylog-time and near-linear work approximation scheme for undirected shortest paths
• Restrictions of minimum spanner problems
• Spanners in graphs of bounded degree
• The 4/3 additive spanner exponent is tight
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Tree Spanners

Cited in

(18)

• Polynomial algorithms for sparse spanners on subcubic graphs
• Approximation of minimum weight spanners for sparse graphs
• NP-completeness of minimum spanner problems
• On Spanners of Geometric Graphs
• An FPT Algorithm for Minimum Additive Spanner Problem.
• scientific article; zbMATH DE number 1629828 (Why is no real title available?)
• Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs
• Sparsification lower bound for linear spanners in directed graphs
• The minimum spanning strong subdigraph problem is fixed parameter tractable
• Complexity of the multiobjective minimum weight minimum stretch spanner problem
• Minimum \(t\)-spanners on subcubic graphs
• Parameterized complexity of directed spanner problems
• scientific article; zbMATH DE number 1107724 (Why is no real title available?)
• Graph spanners: a tutorial review
• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• scientific article; zbMATH DE number 1375574 (Why is no real title available?)
• A PTAS for the sparsest 2-spanner of 4-connected planar triangulations
• Parameterized Complexity of Directed Spanner Problems.

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)