Two algorithms for determining a minimum independent dominating set

DOI10.1080/00207168408803411MaRDI QIDQ3319782zbMATH OpenOpenAlexFDO

Authors Emmanuel Loukakis

Publication date 1984

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207168408803411

zbMATH Keywords

dynamic programming algorithmNP-hardminimum independent dominating setbacktracking algorithmcombinatorial optimaization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• Solving the minimum independent domination set problem in graphs by exact algorithm and greedy heuristic
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• On approximating the minimum independent dominating set

Cites work

• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3299758 (Why is no real title available?)
• A linear algorithm for the domination number of a tree
• Bottleneck extrema
• Disjoint independent dominating sets in graphs
• Dominating Sets in Chordal Graphs
• On covering sets and error-correcting codes
• On the composition and decomposition of clutters
• Optimum domination in weighted trees
• Towards a theory of domination in graphs

Cited in

(4)

• Algorithms to determine an independent dominating set of \(\mathrm{ESC}(n,k)\)
• Bibliography on domination in graphs and some basic definitions of domination parameters
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Solving the minimum independent domination set problem in graphs by exact algorithm and greedy heuristic

This page was built for publication: Two algorithms for determining a minimum independent dominating set

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