An FPT Algorithm for Minimum Additive Spanner Problem.

DOI10.4230/LIPICS.STACS.2020.11OpenAlexW3013721100MaRDI QIDQ5874282FDOQ5874282

Authors: Yusuke Kobayashi 

Publication date: 7 February 2023

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

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

zbMATH Keywords

graph algorithmsfixed-parameter tractabilitygraph spanner

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (1)

• 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)