Exact algorithms for dominating set

DOI10.1016/j.dam.2011.07.001zbMath1237.05157OpenAlexW2070684734WikidataQ59567585 ScholiaQ59567585MaRDI QIDQ411862

Hans L. Bodlaender, Johan M. M. van Rooij

Publication date: 30 April 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.07.001

zbMATH Keywords

dominating setexact algorithmsexponential time algorithmsbranch and reducecomputer aided algorithm designmeasure and conquer

Mathematics Subject Classification ID

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

Related Items (23)

An improved binary programming formulation for the secure domination problem ⋮ Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs ⋮ On the k-rainbow domination in graphs with bounded tree-width ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ A heuristic approximation algorithm of minimum dominating set based on rough set theory ⋮ Parameterized and exact algorithms for class domination coloring ⋮ Exact algorithms for maximum induced matching ⋮ Exact algorithms for weak Roman domination ⋮ Further improvements for SAT in terms of formula length ⋮ Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set} ⋮ THE GEODETIC FAULT TOLERANT DOMINATION NUMBER OF A GRAPH ⋮ The many facets of upper domination ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Computing the differential of a graph: hardness, approximability and exact algorithms ⋮ A linear algorithm for secure domination in trees ⋮ Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems ⋮ Dealing with 4-variables by resolution: an improved MaxSAT algorithm ⋮ Inclusion/exclusion meets measure and conquer ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Near-Optimal Dominating Sets via Random Sampling ⋮ Unnamed Item ⋮ On the complexity of independent dominating set with obligations in graphs ⋮ Exact algorithms for counting 3-colorings of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
• Efficiency in exponential time for domination-type problems
• Which problems have strongly exponential complexity?
• An exact algorithm for the minimum dominating clique problem
• A note on the complexity of minimum dominating set
• Open problems around exact algorithms
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• A measure & conquer approach for the analysis of exact algorithms
• Exact Algorithms for Edge Domination
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• A Bottom-Up Method and Fast Algorithms for max independent set
• Inclusion/Exclusion Meets Measure and Conquer
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• Combinatorial bounds via measure and conquer
• Parameterized and Exact Computation
• Paths, Trees, and Flowers
• A Computing Procedure for Quantification Theory
• STACS 2005
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Exact algorithms for dominating set