Parameterized Complexity of Directed Spanner Problems.

DOI10.4230/LIPICS.IPEC.2020.12OpenAlexW3117654164MaRDI QIDQ6089656FDOQ6089656

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

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)

Cites Work

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

Cited In (3)

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

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)