On the Algorithmic Complexity of Total Domination

DOI10.1137/0605040zbMath0576.68056MaRDI QIDQ3696538

Sandra M. Hedetniemi, Stephen T. Hedetniemi, Renu C. Laskar, John Pfaff

Publication date: 1984

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

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

zbMATH Keywords

tree; linear time algorithm; NP-complete; undirected path graphs; minimum total dominating sets

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

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

05-04: Software, source code, etc. for problems pertaining to combinatorics

Related Items

Total domination in interval graphs, Total domination in interval graphs, Domination in distance-hereditary graphs, On the complexity of the bondage and reinforcement problems, Algorithmic aspects of \(k\)-tuple total domination in graphs, The algorithmic complexity of mixed domination in graphs, The \(p\)-Maxian problem on interval graphs, Efficient algorithms for the conditional covering problem, Bibliography on domination in graphs and some basic definitions of domination parameters, On the complexity of signed and minus total domination in graphs, A survey of selected recent results on total domination in graphs, \(k\)-tuple domination in graphs, A unified approach to domination problems on interval graphs, Labeling algorithms for domination problems in sun-free chordal graphs, Total domination in block graphs, Dominating sets in perfect graphs, Permutation graphs: Connected domination and Steiner trees, The complexity of domination problems in circle graphs, Dominating cliques in chordal graphs, On the computational complexity of upper total domination, The weighted perfect domination problem and its variants, Paired domination on interval and circular-arc graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• A linear algorithm for the domination number of a tree
• Optimum domination in weighted trees
• A recognition algorithm for the intersection graphs of paths in trees
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Total domination in graphs
• Dominating Sets in Chordal Graphs
• Towards a theory of domination in graphs