Parameterized measure \& conquer for problems with no small kernels

DOI10.1007/s00453-011-9566-6zbMath1253.68376OpenAlexW1984814702MaRDI QIDQ1759684

Daniel Binkele-Raible, Henning Fernau

Publication date: 21 November 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-011-9566-6

zbMATH Keywords

analysis of algorithmsgraph problemsmeasure and conquercomputationally hard problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ The price of connectivity for cycle transversals

Cites Work

• Unnamed Item
• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Exact exponential algorithms.
• A new upper bound for Max-2-SAT: A graph-theoretic approach
• Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• On two techniques of combining branching and treewidth
• Vertex and edge covers with clustering properties: Complexity and algorithms
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Equivalence between the minimum covering problem and the maximum matching problem
• Constrained weighted matchings and edge coverings in graphs
• On approximability of the independent/connected edge dominating set problems
• A 2-approximation NC algorithm for connected vertex cover and tree cover
• Parameterized complexity of Vertex Cover variants
• Enumerate and Measure: Improving Parameter Budget Management
• An Amortized Search Tree Analysis for k-Leaf Spanning Tree
• A measure & conquer approach for the analysis of exact algorithms
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• The Curse of Connectivity: t-Total Vertex (Edge) Cover
• A New Algorithm for Finding Trees with Many Leaves
• Incompressibility through Colors and IDs
• Inclusion/Exclusion Meets Measure and Conquer
• Edge Dominating Sets in Graphs
• Theoretical Computer Science
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• Exact and Parameterized Algorithms for Max Internal Spanning Tree

This page was built for publication: Parameterized measure \& conquer for problems with no small kernels