Enumerating minimal connected dominating sets

DOI10.1137/23M1611233MaRDI QIDQ6986949zbMATH OpenFDO

Authors Faisal N. Abu-Khzam, Henning Fernau, Benjamin Gras, Mathieu Liedloff, Kevin Mann

Publication date 7 May 2025

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1611233

zbMATH Keywords

connected dominationdegenerate graphsenumeration problems

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A complexity theory for hard enumeration problems
• A faster algorithm for dominating set analyzed by the potential method
• A measure \& conquer approach for the analysis of exact algorithms
• A note on the complexity of the chromatic number problem
• An exact algorithm for connected red-blue dominating set
• Below all subsets for minimal connected dominating set
• Combinatorial bounds via measure and conquer
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• Enumerating minimal connected dominating sets
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
• Enumeration of minimal connected dominating sets for chordal graphs
• Enumeration of minimal dominating sets and variants
• Exact exponential algorithms.
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1149451 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Inclusion/exclusion meets measure and conquer
• Lower bounds based on the exponential time hypothesis
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Minimal dominating sets in interval graphs and trees
• Minimal Roman dominating functions: extensions and enumeration
• Minimal vertex separators of chordal graphs
• On cliques in graphs
• On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
• On the complexity of solution extension of optimization problems
• On the enumeration of minimal dominating sets and related notions
• On the number of connected sets in bounded degree graphs
• On the number of minimal dominating sets on some graph classes
• Parametrized complexity theory.
• Solving connected dominating set faster than \(2^n\)
• The complexity of dependency detection and discovery in relational databases
• The many facets of upper domination
• The minimal hitting set generation problem: algorithms and computation
• Which problems have strongly exponential complexity?

Cited in

(2)

• Enumerating minimal defensive alliances
• Roman census: enumerating and counting Roman dominating functions on graph classes

This page was built for publication: Enumerating minimal connected dominating sets

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