Algorithm and hardness results on neighborhood total domination in graphs
DOI10.1016/j.tcs.2020.05.002zbMath1458.05197arXiv1910.06423OpenAlexW3024489853MaRDI QIDQ2201995
Anupriya Jha, Dina Pradhan, Sumanta Banerjee
Publication date: 17 September 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1910.06423
NP-completenesspolynomial-time algorithmdominationtotal dominationneighborhood total dominationAPX-completeness
Graph theory (including graph drawing) in computer science (68R10) 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)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation hardness of dominating set problems in bounded degree graphs
- A survey of selected recent results on total domination in graphs
- A linear time recognition algorithm for proper interval graphs
- The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
- Optimization, approximation, and complexity classes
- On the total \(k\)-domination in graphs
- A note on domination and total domination in prisms
- Algorithm complexity of neighborhood total domination and \((\rho,\gamma_{\mathrm{nt}})\)-graphs
- Total forcing versus total domination in cubic graphs
- Integer linear programming models for the weighted total domination problem
- New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
- Trees with large neighborhood total domination number
- Total $k$-domination in strong product graphs
- Bounds on neighborhood total domination in graphs
- Neighbourhood total domination in graphs
- A threshold of ln n for approximating set cover
- A Greedy Heuristic for the Set-Covering Problem
- Dominating Sets in Chordal Graphs
- Total Domination in Graphs
This page was built for publication: Algorithm and hardness results on neighborhood total domination in graphs
