Parameterized complexity of directed spanner problems

DOI10.1007/s00453-021-00911-xOpenAlexW4206179250MaRDI QIDQ2161008

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

Publication date: 3 August 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00911-x

zbMATH Keywords

graph spannersdirected graphsparameterized complexitykernelization

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• NP-completeness of minimum spanner problems
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• Graph spanners: a tutorial review
• The hardness of approximating spanner problems
• 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
• On the hardness of approximating spanners