Measure and conquer: Domination -- a case study

DOI10.1007/11523468_16MaRDI QIDQ5716773zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch

Publication date 10 January 2006

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

Full work available at URL https://doi.org/10.1007/11523468

zbMATH Keywords

Algorithms and data structuresdominating setexponential-time exact algorithmNP-hard problem

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Recommendations

• A measure \& conquer approach for the analysis of exact algorithms
• Design by measure and conquer. A faster exact algorithm for dominating set
• A faster algorithm for dominating set analyzed by the potential method
• Exact (exponential) algorithms for the dominating set problem
• Inclusion/exclusion meets measure and conquer

Cited in

(44)

• Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems
• A bounded search tree algorithm for parameterized face cover
• Efficiency in exponential time for domination-type problems
• On two techniques of combining branching and treewidth
• Pathwidth of cubic graphs and exact algorithms
• Dominating sets in intersection graphs of finite groups
• Inexact graph matching using a hierarchy of matching processes
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Computing optimal Steiner trees in polynomial space
• An exact algorithm for the minimum dominating clique problem
• Improved worst-case complexity for the MIN 3-SET COVERING problem
• A faster algorithm for dominating set analyzed by the potential method
• Turbo-charging dominating set with an FPT subroutine: further improvements and experimental analysis
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• Counting independent sets in claw-free graphs
• A measure \& conquer approach for the analysis of exact algorithms
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• Exact Algorithms for Edge Domination
• Faster Steiner Tree Computation in Polynomial-Space
• Fast exact algorithm for L(2,1)-labeling of graphs
• Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
• Exact algorithms for dominating set
• Moderately exponential approximation: bridging the gap between exact computation and polynomial approximation
• Design by measure and conquer. A faster exact algorithm for dominating set
• On Independent Sets and Bicliques in Graphs
• Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
• Quasiconvex analysis of backtracking algorithms
• scientific article; zbMATH DE number 2222002 (Why is no real title available?)
• Exact (exponential) algorithms for the dominating set problem
• When polynomial approximation meets exact computation
• When polynomial approximation meets exact computation
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• An exact algorithm for connected red-blue dominating set
• Branch and recharge: exact algorithms for generalized domination
• On partitioning a graph into two connected subgraphs
• Improved upper bounds for vertex cover
• Improved edge-coloring with three colors
• An improved exact algorithm for the domatic number problem
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• Solving connected dominating set faster than \(2^n\)
• Exact algorithms for exact satisfiability and number of perfect matchings
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Finding a dominating set on bipartite graphs
• Parameterized algorithms for d-hitting set: the weighted case

This page was built for publication: Measure and conquer: Domination -- a case study

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