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

DOI10.4230/LIPICS.FSTTCS.2012.400MaRDI QIDQ2957516zbMATH OpenFDO

Authors

Publication date 26 January 2017

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

zbMATH Keywords

acyclic subgraphfixed-parameter tractablepolynomial kernel

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: -extendible properties parameterized above the Poljak-Turzík bound
• scientific article; zbMATH DE number 1833409

Cited in

(6)

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

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)