Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs

DOI10.1007/s10878-017-0181-6zbMath1386.05137OpenAlexW2761771983MaRDI QIDQ1702824

Peng Zhang

Publication date: 1 March 2018

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-017-0181-6

zbMATH Keywords

labeled graphalgorithm complexityneighborhood total domination

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) 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

Algorithm and hardness results on neighborhood total domination in graphs, Double vertex-edge domination in graphs: complexity and algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dominating sets for split and bipartite graphs
• A survey of selected recent results on total domination in graphs
• Hardness results and approximation algorithms for (weighted) paired-domination in graphs
• Construction of trees and graphs with equal domination parameters
• Bounds on neighborhood total domination in graphs
• Neighbourhood total domination in graphs
• Total domination in graphs
• Characterizations of trees with equal domination parameters
• A Transition from Total Domination in Graphs to Transversals in Hypergraphs