Total domination and transformation

DOI10.1016/S0020-0190(97)00115-4zbMath1337.68133OpenAlexW1980250259MaRDI QIDQ287166

Dieter Kratsch, Lorna K. Stewart

Publication date: 26 May 2016

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00115-4

zbMATH Keywords

design of algorithmsdominationefficient algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Algorithmic Aspects of Disjunctive Total Domination in Graphs ⋮ Domination and total domination on asteroidal triple-free graphs ⋮ Homogeneous sets and domination: A linear time algorithm for distance?hereditary graphs ⋮ Domination in rose window graphs ⋮ On total \(f\)-domination: polyhedral and algorithmic results ⋮ 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 ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width

Cites Work

• Domination in convex and chordal bipartite graphs
• Dominating sets in perfect graphs
• An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph