An FPT Algorithm for Minimum Additive Spanner Problem.

DOI10.4230/LIPICS.STACS.2020.11MaRDI QIDQ5874282zbMATH OpenOpenAlexFDO

Authors Yusuke Kobayashi

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/1903.01047

zbMATH Keywords

graph algorithmsfixed-parameter tractabilitygraph spanner

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Additivity in minimum cost spanning tree problems
• Additive Sparsification of CSPs.
• The Sparsest Additive Spanner via Multiple Weighted BFS Trees
• The sparsest additive spanner via multiple weighted BFS trees
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs
• A hierarchy of lower bounds for sublinear additive spanners
• A Hierarchy of Lower Bounds for Sublinear Additive Spanners
• Near-additive spanners in low polynomial deterministic CONGEST time
• FPT algorithms for domination in sparse graphs and beyond

Cited in

(2)

• Parameterized complexity of directed spanner problems
• Parameterized Complexity of Directed Spanner Problems.

This page was built for publication: An FPT Algorithm for Minimum Additive Spanner Problem.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874282)