Exact algorithms for dominating set
DOI10.1016/J.DAM.2011.07.001zbMATH Open1237.05157OpenAlexW2070684734WikidataQ59567585 ScholiaQ59567585MaRDI QIDQ411862FDOQ411862
Authors: 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
Recommendations
dominating setexact algorithmsmeasure and conquerbranch and reducecomputer aided algorithm designexponential time algorithms
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Title not available (Why is that?)
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- A measure & conquer approach for the analysis of exact algorithms
- Title not available (Why is that?)
- Paths, Trees, and Flowers
- Which problems have strongly exponential complexity?
- Combinatorial bounds via measure and conquer
- A Computing Procedure for Quantification Theory
- Graph-Theoretic Concepts in Computer Science
- Algorithms for maximum independent sets
- Open problems around exact algorithms
- Exact Algorithms for Edge Domination
- Finding a Maximum Independent Set
- Efficiency in exponential time for domination-type problems
- An exact algorithm for the minimum dominating clique problem
- A note on the complexity of minimum dominating set
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parameterized and Exact Computation
- STACS 2005
Cited In (28)
- Exact and heuristic algorithms for the domination problem
- On the k-rainbow domination in graphs with bounded tree-width
- An improved binary programming formulation for the secure domination problem
- Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}
- THE GEODETIC FAULT TOLERANT DOMINATION NUMBER OF A GRAPH
- A linear algorithm for secure domination in trees
- Exact algorithms for maximum induced matching
- Title not available (Why is that?)
- Faster Computation of the Maximum Dissociation Set and Minimum 3-Path Vertex Cover in Graphs
- Parameterized and exact algorithms for class domination coloring
- Parameterized and Exact Algorithms for Class Domination Coloring
- Domination polynomials of the grid, the cylinder, the torus, and the king graph
- A heuristic approximation algorithm of minimum dominating set based on rough set theory
- A decidability result for the dominating set problem
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Exact algorithms for counting 3-colorings of graphs
- Generating Faster Algorithms for d-Path Vertex Cover
- Algorithmic Aspects of Upper Domination: A Parameterised Perspective
- The many facets of upper domination
- On the complexity of independent dominating set with obligations in graphs
- A polynomial-time approximation to a minimum dominating set in a graph
- Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
- Exact algorithms for problems related to the densest \(k\)-set problem
- Dealing with 4-variables by resolution: an improved MaxSAT algorithm
- Inclusion/exclusion meets measure and conquer
- Exact algorithms for weak Roman domination
- Near-Optimal Dominating Sets via Random Sampling
- Further improvements for SAT in terms of formula length
This page was built for publication: Exact algorithms for dominating set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q411862)
