On the Algorithmic Complexity of Total Domination

DOI10.1137/0605040zbMATH Open0576.68056OpenAlexW2000760879MaRDI QIDQ3696538FDOQ3696538

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

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

Recommendations

• Total domination in block graphs
• On the algorithmic complexity of edge total domination
• Algorithmic aspects of disjunctive total domination in graphs
• scientific article; zbMATH DE number 4051684
• Total domination in interval graphs

zbMATH Keywords

treeNP-completelinear time algorithmundirected path graphsminimum total dominating sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Cites Work

• Title not available (Why is that?)
• Total domination in graphs
• Title not available (Why is that?)
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Towards a theory of domination in graphs
• Domination, independent domination, and duality in strongly chordal graphs
• A linear algorithm for the domination number of a tree
• A recognition algorithm for the intersection graphs of paths in trees
• Dominating Sets in Chordal Graphs
• Title not available (Why is that?)
• Optimum domination in weighted trees
• Title not available (Why is that?)

Cited In (62)

• Algorithmic and complexity aspects of problems related to total restrained domination for graphs
• An efficient algorithm for distance total domination in block graphs
• Edge open packing: complexity, algorithmic aspects, and bounds
• A knowledge-based iterated local search for the weighted total domination problem
• The strong domination problem in block graphs and proper interval graphs
• Dominating cliques in chordal graphs
• Title not available (Why is that?)
• On the algorithmic complexity of \(k\)-tuple total domination
• Title not available (Why is that?)
• A linear time algorithm for liar's domination problem in proper interval graphs
• Complexity and monotonicity results for domination games
• Permutation graphs: Connected domination and Steiner trees
• The \(p\)-Maxian problem on interval graphs
• On the complexity of the bondage and reinforcement problems
• Labeling algorithms for domination problems in sun-free chordal graphs
• Title not available (Why is that?)
• The complexity of domination problems in circle graphs
• Total domination in block graphs
• Paired-domination problem on distance-hereditary graphs
• A survey of selected recent results on total domination in graphs
• On total \(f\)-domination: polyhedral and algorithmic results
• Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Total domination and transformation
• On the computational complexity of upper total domination
• On the complexity of signed and minus total domination in graphs
• On the algorithmic complexity of edge total domination
• The algorithmic complexity of mixed domination in graphs
• Algorithmic and complexity aspects of problems related to total Roman domination for graphs
• Paired domination on interval and circular-arc graphs
• Dominating sets in perfect graphs
• \(k\)-tuple domination in graphs
• Dominated colorings of graphs
• On some domination colorings of graphs
• Exact and heuristic algorithms for the weighted total domination problem
• Total 2-domination of proper interval graphs
• On bondage numbers of graphs: a survey with some comments
• Hardness results and approximation algorithm for total liar's domination in graphs
• Efficient algorithms for the conditional covering problem
• Algorithmic aspects of disjunctive total domination in graphs
• A decidability result for the dominating set problem
• Algorithmic and NP-completeness aspects of a total lict domination number of a graph
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• Domination on Cocomparability Graphs
• On independent \([1, 2]\)-sets in trees
• Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs
• The minimum dominating tree problem for graphs
• The weighted perfect domination problem and its variants
• Complexity of Total {k}-Domination and Related Problems
• Total domination in interval graphs
• Total domination in interval graphs
• On the independence transversal total domination number of graphs
• Closed formulas for the total Roman domination number of lexicographic product graphs
• A unified approach to domination problems on interval graphs
• Title not available (Why is that?)
• Domination in distance-hereditary graphs
• Essential upper bounds on the total domination number
• Covering graphs with convex sets and partitioning graphs into convex sets
• Title not available (Why is that?)
• Liar's domination in graphs: complexity and algorithm
• Title not available (Why is that?)
• Revising Johnson's table for the 21st century

This page was built for publication: On the Algorithmic Complexity of Total Domination

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