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

algorithmNP-completenessedge total dominationundirected path graphs

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• 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)

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

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)