A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance

DOI10.1007/978-3-642-13073-1_28MaRDI QIDQ3563012zbMATH OpenOpenAlexFDO

Authors Daniel Binkele-Raible, Ljiljana Brankovic, Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Peter Rossmanith

Publication date 28 May 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13073-1_28

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Recommendations

• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack
• Mathematical Foundations of Computer Science 2005
• The complexity of irredundant sets parameterized by size
• scientific article; zbMATH DE number 512844
• scientific article; zbMATH DE number 1405801
• On the structure of parameterized problems in NP
• Extended abstract for
• The parameterized complexity of the equidomination problem
• ``NP\(=\)P? and restricted partitions

Cited in

(2)

• An exact exponential-time algorithm for the directed maximum leaf spanning tree problem
• Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack

This page was built for publication: A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance

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