Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack

DOI10.1016/j.jda.2011.03.002zbMath1225.05227OpenAlexW2165086965MaRDI QIDQ635734

Marek Cygan, Mathieu Liedloff, Henning Fernau, Dieter Kratsch, Joachim Kneis, Peter Rossmanith, Jakub Onufry Wojtaszczyk, Ljiljana Brankovic, Daniel Binkele-Raible, Alexander Langer, Marcin Pilipczuk

Publication date: 23 August 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.03.002

zbMATH Keywords

graph algorithmsirredundance number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (16)

Enumeration of Maximal Irredundant Sets for Claw-Free Graphs ⋮ On the number of connected sets in bounded degree graphs ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Solving target set selection with bounded thresholds faster than \(2^n\) ⋮ The many facets of upper domination ⋮ An exact exponential-time algorithm for the directed maximum leaf spanning tree problem ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ Solving Target Set Selection with Bounded Thresholds Faster than 2^n ⋮ Scheduling partially ordered jobs faster than \(2^n\) ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ On the Complexity Landscape of the Domination Chain ⋮ Irredundance ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Moderately exponential time algorithms for the maximum induced matching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• On domination and independent domination numbers of a graph
• The irredundance number and maximum degree of a graph
• Parameterized algorithms for feedback set problems and their duals in tournaments
• The parameterized complexity of the induced matching problem
• Two relations between the parameters of independence and irredundance
• Contributions to the theory of domination, independence and irredundance in graphs
• A note on the irredundance number after vertex deletion
• Total irredundance in graphs
• The complexity of irredundant sets parameterized by size
• Parametrized complexity theory.
• Weighted irredundance of interval graphs.
• Graph-theoretic parameters concerning domination, independence, and irredundance
• A measure & conquer approach for the analysis of exact algorithms
• Kernels: Annotated, Proper and Induced
• The Travelling Salesman Problem in Bounded Degree Graphs
• Fourier meets M\"{o}bius: fast subset convolution
• Set Partitioning via Inclusion-Exclusion
• Irredundant Set Faster Than O(2 n )
• A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Inclusion/Exclusion Meets Measure and Conquer
• Properties of Hereditary Hypergraphs and Middle Graphs
• The Private Neighbor Cube
• Irredundance and Maximum Degree in Graphs
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack