Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs

DOI10.1007/978-3-540-77891-2_14zbMATH Open1132.05326OpenAlexW1833689605MaRDI QIDQ5452161FDOQ5452161

Authors Henning Fernau, Daniel Raible

Publication date 25 March 2008

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-77891-2_14

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
• scientific article; zbMATH DE number 176747
• scientific article; zbMATH DE number 1833409
• Acyclic colorings of subcubic graphs
• Directed acyclic subgraph problem parameterized above the Poljak-Turzík bound

Cites work

• scientific article; zbMATH DE number 432770 (Why is no real title available?)
• scientific article; zbMATH DE number 6118220 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1833409 (Why is no real title available?)
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• Automata, Languages and Programming
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• Improved Algorithms for the Feedback Vertex Set Problems
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Parameterized Algorithms for Hitting Set: The Weighted Case
• Parameterizing MAX SNP Problems Above Guaranteed Values
• Reducibility among combinatorial problems

Cited in

(7)

• Bayesian network learning via topological order
• Parameterized measure \& conquer for problems with no small kernels
• Tight Bounds for the Maximum Acyclic Subgraph Problem
• A cubic algorithm for the directed Eulerian subgraph problem
• An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
• Enumerate and measure: improving parameter budget management
• scientific article; zbMATH DE number 1833409 (Why is no real title available?)

This page was built for publication: Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs

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