The algorithmic complexity of mixed domination in graphs
From MaRDI portal
Publication:533883
DOI10.1016/j.tcs.2011.01.029zbMath1216.68119OpenAlexW2021417413MaRDI 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
Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination ⋮ Mixed domination and 2-independence in trees ⋮ On the algorithmic complexity of edge total domination ⋮ Signed mixed Roman domination numbers in graphs ⋮ Mixed Roman domination in graphs ⋮ Total mixed domination in graphs ⋮ \([1,2\)-sets and \([1,2]\)-total sets in trees with algorithms] ⋮ On the complexity of variations of mixed domination on graphs† ⋮ Unnamed Item ⋮ Improved budgeted connected domination and budgeted edge-vertex domination ⋮ An efficient algorithm for distance total domination in block graphs ⋮ The strong domination problem in block graphs and proper interval graphs ⋮ Upper and lower bounds on approximating weighted mixed domination ⋮ Improved parameterized algorithms and kernels for mixed domination ⋮ Signed mixed dominating functions in complete bipartite graphs ⋮ Law of large numbers for a two-dimensional class cover problem
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
