A Polynomial Kernel for Funnel Arc Deletion Set.

DOI10.4230/LIPICS.IPEC.2020.13MaRDI QIDQ6089658zbMATH OpenOpenAlexFDO

Authors

Publication date 13 November 2023

Full work available at URL http://arxiv.org/pdf/1911.05520.pdf

zbMATH Keywords

kernelsparameterized algorithmgraph editingfunnelsdirected feedback arc set

Mathematics Subject Classification ID

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

Recommendations

• A polynomial kernel for funnel arc deletion set
• Polynomial kernels for deletion to classes of acyclic digraphs
• Polynomial kernels for deletion to classes of acyclic digraphs
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• Towards a polynomial kernel for directed feedback vertex set

Cites work

• A fixed-parameter algorithm for the directed feedback vertex set problem
• A kernelization algorithm for \(d\)-hitting set
• Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
• Fundamentals of parameterized complexity
• Kernelization -- preprocessing with a guarantee
• Kernelization. Theory of parameterized preprocessing
• Kernels for deletion to classes of acyclic digraphs
• Parameterized algorithms
• Polynomial kernels for deletion to classes of acyclic digraphs
• Recent developments in kernelization: a survey
• Wannabe bounded treewidth graphs admit a polynomial kernel for DFVS

Cited in

(1)

• A polynomial kernel for funnel arc deletion set

This page was built for publication: A Polynomial Kernel for Funnel Arc Deletion Set.

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