On the Algorithmic Complexity of Total Domination
From MaRDI portal
Publication:3696538
DOI10.1137/0605040zbMath0576.68056OpenAlexW2000760879MaRDI QIDQ3696538
Sandra M. Hedetniemi, John Pfaff, 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
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Software, source code, etc. for problems pertaining to combinatorics (05-04)
Related Items (47)
On the algorithmic complexity of edge total domination ⋮ Paired domination on interval and circular-arc graphs ⋮ On independent \([1, 2\)-sets in trees] ⋮ A unified approach to domination problems on interval graphs ⋮ On some domination colorings of graphs ⋮ Labeling algorithms for domination problems in sun-free chordal graphs ⋮ The weighted perfect domination problem and its variants ⋮ Total domination in block graphs ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ The \(p\)-Maxian problem on interval graphs ⋮ On the algorithmic complexity of \(k\)-tuple total domination ⋮ On the complexity of the bondage and reinforcement problems ⋮ Algorithmic Aspects of Disjunctive Total Domination in Graphs ⋮ Algorithmic and complexity aspects of problems related to total restrained domination for graphs ⋮ Liar's domination in graphs: complexity and algorithm ⋮ On bondage numbers of graphs: a survey with some comments ⋮ On the computational complexity of upper total domination ⋮ Algorithmic aspects of \(k\)-tuple total domination in graphs ⋮ A linear time algorithm for liar's domination problem in proper interval graphs ⋮ Dominating sets in perfect graphs ⋮ Permutation graphs: Connected domination and Steiner trees ⋮ On total \(f\)-domination: polyhedral and algorithmic results ⋮ Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs ⋮ On the independence transversal total domination number of graphs ⋮ Essential upper bounds on the total domination number ⋮ Efficient algorithms for the conditional covering problem ⋮ Total domination in interval graphs ⋮ Total domination in interval graphs ⋮ The algorithmic complexity of mixed domination in graphs ⋮ The complexity of domination problems in circle graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Hardness results and approximation algorithm for total liar's domination in graphs ⋮ Exact and heuristic algorithms for the weighted total domination problem ⋮ On the complexity of signed and minus total domination in graphs ⋮ Domination in distance-hereditary graphs ⋮ A survey of selected recent results on total domination in graphs ⋮ An efficient algorithm for distance total domination in block graphs ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ Total 2-domination of proper interval graphs ⋮ \(k\)-tuple domination in graphs ⋮ Closed formulas for the total Roman domination number of lexicographic product graphs ⋮ Algorithmic and complexity aspects of problems related to total Roman domination for graphs ⋮ Covering graphs with convex sets and partitioning graphs into convex sets ⋮ Revising Johnson's table for the 21st century ⋮ Dominated colorings of graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Dominating cliques in chordal 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
This page was built for publication: On the Algorithmic Complexity of Total Domination
