Parameterized Complexity of Directed Spanner Problems.

DOI10.4230/lipics.ipec.2020.12OpenAlexW3117654164MaRDI QIDQ6089656

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

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

graph spannersdirected graphsparameterized complexitykernelization

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• NP-completeness of minimum spanner problems
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Graph spanners
• Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
• Kernelization
• An Optimal Synchronizer for the Hypercube
• Roundtrip spanners and roundtrip routing in directed graphs
• Additive graph spanners
• Parameterized Algorithms
• An FPT Algorithm for Minimum Additive Spanner Problem.
• On the hardness of approximating spanners

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