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

DOI10.4230/LIPICS.FSTTCS.2012.400zbMATH Open1354.68116arXiv1207.3586MaRDI QIDQ2957516FDOQ2957516

Authors:

Publication date: 26 January 2017

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

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

zbMATH Keywords

polynomial kernelfixed-parameter tractableacyclic subgraph

Mathematics Subject Classification ID

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

Cited In (6)

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

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)