Enumerate and Measure: Improving Parameter Budget Management

DOI10.1007/978-3-642-17493-3_6zbMath1309.68235OpenAlexW2116671197MaRDI QIDQ3058690

Henning Fernau, Daniel Binkele-Raible

Publication date: 7 December 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-17493-3_6

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Related Items (14)

On approximating (connected) 2-edge dominating set by a tree ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ A multivariate framework for weighted FPT algorithms ⋮ New Results on Directed Edge Dominating Set ⋮ Parameterized edge dominating set in graphs with degree bounded by 3 ⋮ New parameterized algorithms for the edge dominating set problem ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Contracting graphs to paths and trees ⋮ A refined exact algorithm for edge dominating set ⋮ Inclusion/exclusion meets measure and conquer ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set

Cites Work

• Unnamed Item
• 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
• A 2-approximation NC algorithm for connected vertex cover and tree cover
• Parameterized complexity of Vertex Cover variants
• 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
• Exact Algorithms for Edge Domination
• A New Algorithm for Finding Trees with Many Leaves
• Incompressibility through Colors and IDs
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• 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: Enumerate and Measure: Improving Parameter Budget Management