On the algorithmic complexity of edge total domination

DOI10.1016/J.TCS.2014.08.005MaRDI QIDQ300244zbMATH OpenOpenAlexFDO

Authors Lianying Miao, Yancai Zhao, Zuhua 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

algorithmedge total dominationNP-completenessundirected path graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The complexity of total edge domination and some related results on trees
• Complexity and characterization aspects of edge-related domination for graphs
• On the Algorithmic Complexity of Total Domination
• The algorithmic complexity of mixed domination in graphs
• Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs

Cites work

• 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
• Dominating Sets in Chordal Graphs
• Edge Dominating Sets in Graphs
• Edge domination in graphs
• scientific article; zbMATH DE number 437479 (Why is no real title available?)
• scientific article; zbMATH DE number 3674114 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1302196 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Minimum Edge Dominating Sets
• On the Algorithmic Complexity of Total Domination
• On the mixed domination problem in graphs
• Rainbow domination on trees
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• The algorithmic complexity of mixed domination in graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Two classes of edge domination in graphs

Cited in

(12)

• Perfect edge domination: hard and solvable cases
• Complexity and lowers bounds for power edge set problem
• Complexity and inapproximability results for the power edge set problem
• An NP-completeness result of edge search in graphs
• The complexity of total edge domination and some related results on trees
• Complexity and characterization aspects of edge-related domination for graphs
• Algorithmic aspects of upper edge domination
• The computational complexity of the edge-perfect graph and the totally balanced packing game recognition problems
• On the Algorithmic Complexity of Total Domination
• On total vertex covers and edge domination in graphs
• scientific article; zbMATH DE number 7481760 (Why is no real title available?)
• Algorithms and hardness results for edge total domination problem in graphs

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

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