Directed acyclic subgraph problem parameterized above the Poljak-Turzík bound

DOI10.4230/LIPICS.FSTTCS.2012.400MaRDI QIDQ2957516zbMATHFDO

Authors

Publication date 26 January 2017

Full work available at URL https://arxiv.org/abs/1207.3586

zbMATH Keywords

polynomial kernelfixed-parameter tractableacyclic subgraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Tight Bounds for the Maximum Acyclic Subgraph Problem
• Parameterized complexity of the induced subgraph problem in directed graphs
• Parameterized complexity of directed feedback set problems in tournaments.
• Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
• scientific article; zbMATH DE number 1833409

Cited in

(6)

• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• Maximum balanced subgraph problem parameterized above lower bound
• Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Linear kernels and linear-time algorithms for finding large cuts
• Acyclic digraphs

This page was built for publication: Directed acyclic subgraph problem parameterized above the Poljak-Turzík bound

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