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

DOI10.1016/j.tcs.2018.06.031zbMath1401.68098OpenAlexW2810702411MaRDI QIDQ1784745

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

planar graphsNP-hardnessFPT algorithmdegree-bounded graphsminimum spanner problem

Mathematics Subject Classification ID

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