Parameterized algorithms for generalizations of directed feedback vertex set

DOI10.1016/J.DISOPT.2022.100740OpenAlexW3009264021MaRDI QIDQ5925617FDOQ5925617

Alexander Göke, Matthias Mnich, Dániel Marx

Publication date: 16 February 2023

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2022.100740

zbMATH Keywords

fixed-parameter algorithmsdirected feedback vertex set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• The directed subgraph homeomorphism problem
• Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Approximating minimum feedback sets and multicuts in directed graphs
• Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
• Divide-and-conquer approximation algorithms via spreading metrics
• Computing the Deficiency of Housing Markets with Duplicate Houses
• Packing directed circuits fractionally
• Parameterized complexity of Eulerian deletion problems
• On the computational complexity of vertex integrity and component order connectivity
• What’s Next? Future Directions in Parameterized Complexity
• Component order connectivity in directed graphs
• Linear kernels for separating a graph into components of bounded size
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• DAG-width and circumference of digraphs
• Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
• Parameterized algorithms for generalizations of directed feedback vertex set
• Simple proof of hardness of feedback vertex set

Cited In (4)

• New Parameterized Algorithms for APSP in Directed Graphs
• Title not available (Why is that?)
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• A fixed-parameter algorithm for the directed feedback vertex set problem

This page was built for publication: Parameterized algorithms for generalizations of directed feedback vertex set

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