Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs

DOI10.1016/j.ipl.2018.06.007zbMath1458.05185OpenAlexW2810200233MaRDI QIDQ1653049

V. Leoni, Pablo Torres, Gabriela R. Argiroffo

Publication date: 17 July 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.06.007

zbMATH Keywords

computational complexitybipartite graph\(k\)-tuple total dominationtotal \(\{k\}\)-domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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 (3)

Multiple Domination ⋮ 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
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• \(k\)-tuple total domination in graphs
• Completely separable graphs
• On the total \(\{k\}\)-domination number of Cartesian products of graphs
• Distance-hereditary graphs
• Some APX-completeness results for cubic graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Approximating clique-width and branch-width
• Complexity of Total {k}-Domination and Related Problems
• Total domination in graphs
• Total Domination in Graphs
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs

This page was built for publication: Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs