Algorithms and Computation

DOI10.1007/11602613MaRDI QIDQ5897890zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Fabrizio Grandoni, Artem Pyatkin, Alexey A. Stepanov

Publication date 14 November 2006

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

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

zbMATH Keywords

domatic numberminimum dominating setminimum set coverexact (exponential) algorithmsweighted dominating set

Mathematics Subject Classification ID

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

Recommendations

• Combinatorial bounds via measure and conquer
• Counting Minimum Weighted Dominating Sets
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On maximum number of minimal dominating sets in graphs
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration

Cited in

(18)

• On the maximum number of minimum dominating sets in forests
• Maximum dissociation sets in subcubic trees
• An improved exact algorithm for the domatic number problem
• Counting dominating sets and related structures in graphs
• Combinatorial bounds via measure and conquer
• The parameterized complexity of maximality and minimality problems
• A faster algorithm for dominating set analyzed by the potential method
• Enumeration and maximum number of minimal connected vertex covers in graphs
• On two techniques of combining branching and treewidth
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Maximal and maximum dissociation sets in general and triangle-free graphs
• Polynomial space algorithms for counting dominating sets and the domatic number
• A note on the complexity of minimum dominating set
• Minimum number of maximal dissociation sets in trees
• Trimmed Moebius inversion and graphs of bounded degree
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Inclusion/Exclusion Meets Measure and Conquer
• Counting Minimum Weighted Dominating Sets

This page was built for publication: Algorithms and Computation

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