The algorithmic complexity of mixed domination in graphs

DOI10.1016/j.tcs.2011.01.029zbMath1216.68119MaRDI QIDQ533883

Moo Young Sohn, Yan-Cai Zhao, Li-ying Kang

Publication date: 10 May 2011

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

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

zbMATH Keywords

tree; algorithm; split graph; NP-complete; mixed domination

Mathematics Subject Classification ID

05C05: Trees

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

Law of large numbers for a two-dimensional class cover problem, Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination, The strong domination problem in block graphs and proper interval graphs, Signed mixed dominating functions in complete bipartite graphs, An efficient algorithm for distance total domination in block graphs, Upper and lower bounds on approximating weighted mixed domination, Unnamed Item, Total mixed domination in graphs, On the algorithmic complexity of edge total domination, Signed mixed Roman domination numbers in graphs, \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms], Mixed Roman domination in graphs, Mixed domination and 2-independence in trees, Improved budgeted connected domination and budgeted edge-vertex domination, Improved parameterized algorithms and kernels for mixed domination, On the complexity of variations of mixed domination on graphs^†

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Dominating sets for split and bipartite graphs
• Characterizations of strongly chordal graphs
• On total covers of graphs
• A linear algorithm for the domination number of a tree
• Some simplified NP-complete graph problems
• On total matching numbers and total covering numbers of complementary graphs
• Optimum domination in weighted trees
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• Edge domination in graphs
• A characterization of strongly chordal graphs
• On the Algorithmic Complexity of Total Domination
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Domination and location in acyclic graphs
• Three Partition Refinement Algorithms
• Edge Dominating Sets in Graphs
• Dominating Sets in Chordal Graphs
• A recognition algorithm for the total graphs
• Total matchings and total coverings of graphs