Parameterized Complexity of Directed Spanner Problems.

DOI10.4230/LIPICS.IPEC.2020.12MaRDI QIDQ6089656zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Petr A. Golovach, William Lochet, Pranabendu Misra, Saket Saurabh, Roohani Sharma

Publication date 13 November 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2020/13315/pdf/LIPIcs-IPEC-2020-12.pdf/

zbMATH Keywords

directed graphsparameterized complexitykernelizationgraph spanners

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Parameterized complexity of directed spanner problems
• An FPT Algorithm for Minimum Additive Spanner Problem.
• Sparsification lower bound for linear spanners in directed graphs
• Finding sparser directed spanners
• NP-hardness and fixed-parameter tractability of the minimum spanner problem

Cites work

• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• Additive graph spanners
• An FPT Algorithm for Minimum Additive Spanner Problem.
• An Optimal Synchronizer for the Hypercube
• Approximating spanners and directed Steiner forest: upper and lower bounds
• Fundamentals of parameterized complexity
• Graph spanners
• Kernelization. Theory of parameterized preprocessing
• NP-completeness of minimum spanner problems
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• On the hardness of approximating spanners
• Parameterized algorithms
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Roundtrip spanners and roundtrip routing in directed graphs

Cited in

(4)

• New Parameterized Algorithms for APSP in Directed Graphs
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Complexity of the directed spanning cactus problem
• Parameterized complexity of directed spanner problems

This page was built for publication: Parameterized Complexity of Directed Spanner Problems.

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