An exact algorithm for connected red-blue dominating set

DOI10.1016/j.jda.2011.03.006zbMath1225.05226OpenAlexW1969151326MaRDI QIDQ635737

Faisal N. Abu-Khzam, Amer E. Mouawad, Mathieu Liedloff

Publication date: 23 August 2011

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.03.006

zbMATH Keywords

dominating setexact algorithmsweighted Steiner tree

Mathematics Subject Classification ID

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

Related Items

Enumerating minimal connected dominating sets in graphs of bounded chordality ⋮ Bounds for the connected domination number of maximal outerplanar graphs ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size ⋮ On the parameterized complexity of dynamic problems ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ Below All Subsets for Minimal Connected Dominating Set ⋮ An improved exact algorithm for minimum dominating set in chordal graphs ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ Linear algorithms for red and blue domination in convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving connected dominating set faster than \(2^n\)
• Fourier meets M\"{o}bius: fast subset convolution
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Inclusion/Exclusion Meets Measure and Conquer
• An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Algorithms – ESA 2005
• Automata, Languages and Programming

This page was built for publication: An exact algorithm for connected red-blue dominating set