Parameterized Complexity of Directed Spanner Problems.

DOI10.4230/LIPICS.IPEC.2020.12OpenAlexW3117654164MaRDI QIDQ6089656FDOQ6089656

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/

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

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. Theory of parameterized preprocessing
• 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)