On the algorithmic complexity of \(k\)-tuple total domination

DOI10.1016/j.dam.2014.04.007zbMath1298.05254OpenAlexW2043346507MaRDI QIDQ400524

Gerard Jennhwa Chang, James K. Lan

Publication date: 22 August 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.04.007

zbMATH Keywords

algorithmNP-completeblock graphtotal dominationcactus\(k\)-tuple total dominationundirected path graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Total 2-domination of proper interval graphs ⋮ Unnamed Item ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs ⋮ A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• \(k\)-tuple total domination in graphs
• A survey of selected recent results on total domination in graphs
• Total domination in block graphs
• A recognition algorithm for the intersection graphs of paths in trees
• Algorithmic aspect of \(k\)-tuple domination in graphs.
• \(k\)-tuple total domination in cross products of graphs
• Algorithmic aspects of the \(k\)-domination problem in graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Strong Transversals in Hypergraphs and Double Total Domination in Graphs
• COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS
• On the Algorithmic Complexity of Total Domination
• Representations of chordal graphs as subtrees of a tree
• Total domination in graphs
• Total Domination in Graphs

This page was built for publication: On the algorithmic complexity of \(k\)-tuple total domination