Algorithmic aspects of secure connected domination in graphs

DOI10.7151/dmgt.2260zbMath1468.05212arXiv2001.11250OpenAlexW2989839253MaRDI QIDQ2042631

P. Venkata Subba Reddy, Jakkepalli Pavan Kumar

Publication date: 21 July 2021

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.11250

zbMATH Keywords

chordal graphstree-widthcomplexity classessecure domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (3)

Algorithmic aspects of outer independent Roman domination in graphs ⋮ Secure connected domination and secure total domination in unit disk graphs and rectangle graphs ⋮ Algorithmic aspects of 2-secure domination in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic aspects of \(b\)-disjunctive domination in graphs
• Dominating sets for split and bipartite graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Some APX-completeness results for cubic graphs
• The complexity of secure domination problem in graphs
• Algorithmic aspects of semitotal domination in graphs
• Edge criticality in secure graph domination
• On secure domination in graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• Two Hardness Results on Feedback Vertex Sets
• Approximation algorithms for connected dominating sets
• Algorithmic complexity of secure connected domination in graphs
• Reducibility among Combinatorial Problems
• Doubly chordal graphs, steiner trees, and connected domination
• Node-and edge-deletion NP-complete problems
• Algorithms and Computation

This page was built for publication: Algorithmic aspects of secure connected domination in graphs