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

DOI10.1007/978-3-540-77891-2_14zbMath1132.05326OpenAlexW1833689605MaRDI QIDQ5452161

Daniel Raible, Henning Fernau

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

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

Related Items

An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set} ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ Enumerate and Measure: Improving Parameter Budget Management ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Finding a Minimum Feedback Vertex Set in Time $\mathcal{O} (1.7548^n)$
• Improved Algorithms for the Feedback Vertex Set Problems
• An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Reducibility among Combinatorial Problems
• Automata, Languages and Programming

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