On the algorithmic complexity of edge total domination

DOI10.1016/j.tcs.2014.08.005zbMath1338.68123OpenAlexW1981232799MaRDI QIDQ300244

Lian-Ying Miao, Yan-Cai Zhao, Zu-hua Liao

Publication date: 27 June 2016

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

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

zbMATH Keywords

algorithmNP-completenessedge total dominationundirected path graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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)

Algorithms and hardness results for edge total domination problem in graphs ⋮ Unnamed Item ⋮ The complexity of total edge domination and some related results on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The algorithmic complexity of mixed domination in graphs
• Rainbow domination on trees
• A linear algorithm for finding a minimum dominating set in a cactus
• A linear algorithm for the domination number of a tree
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Edge domination in graphs
• On the mixed domination problem in graphs
• Two classes of edge domination in graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Minimum Edge Dominating Sets
• On the Algorithmic Complexity of Total Domination
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Edge Dominating Sets in Graphs
• Dominating Sets in Chordal Graphs

This page was built for publication: On the algorithmic complexity of edge total domination