Differentiating-total domination: approximation and hardness results

DOI10.1016/J.TCS.2021.05.021MaRDI QIDQ2034786zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 23 June 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.05.021

zbMATH Keywords

\textsf{APX}-complete\textsf{NP}-completedifferentiating-total dominationdominationpolynomial-time algorithmtotal domination

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Global total \(k\)-domination: approximation and hardness results
• B-disjunctive total domination in graphs: algorithm and hardness results
• Algorithm and hardness results on neighborhood total domination in graphs
• Secure total domination in graphs: bounds and complexity
• Algorithmic aspects of semitotal domination in graphs

Cites work

• A note on the complexity of locating-total domination in graphs
• A review of tree convex sets test
• A survey of selected recent results on total domination in graphs
• Analytical approach to parallel repetition
• Approximation hardness of dominating set problems in bounded degree graphs
• Bounds on the differentiating-total domination number of a tree
• Domination in convex and chordal bipartite graphs
• Domination in some subclasses of bipartite graphs
• scientific article; zbMATH DE number 3495588 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Locating and total dominating sets in trees
• On locating and differetiating-total domination in trees
• Reducibility among combinatorial problems
• Some APX-completeness results for cubic graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Total domination in graphs

Cited in

(2)

• Algorithm and hardness results on neighborhood total domination in graphs
• Bounds and extremal graphs for total dominating identifying codes

This page was built for publication: Differentiating-total domination: approximation and hardness results

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