Counting Minimum Weighted Dominating Sets

DOI10.1007/978-3-540-73545-8_18MaRDI QIDQ3608842zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Alexey A. Stepanov

Publication date 6 March 2009

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

Full work available at URL https://doi.org/10.1007/978-3-540-73545-8_18

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Computation
• Inclusion/Exclusion Meets Measure and Conquer
• Combinatorial bounds via measure and conquer
• Counting minimal dominating sets
• An \(O ^{*}(1.1939^{n })\) time algorithm for minimum weighted dominating induced matching

Cited in

(5)

• Bounds on the maximum number of minimum dominating sets
• Bicolored independent sets and bicliques
• scientific article; zbMATH DE number 5990006 (Why is no real title available?)
• Algorithms and Computation
• Inclusion/Exclusion Meets Measure and Conquer

This page was built for publication: Counting Minimum Weighted Dominating Sets

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