Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs

DOI10.7155/JGAA.00334MaRDI QIDQ2938747zbMATH OpenOpenAlexFDO

Authors B. S. Panda, Arti Pandey

Publication date 15 January 2015

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/jgaa.00334

zbMATH Keywords

minimum outer-connected domination problemouter-connected domination decision problem

Mathematics Subject Classification ID

Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Algorithm and hardness results for outer-connected dominating set in graphs
• On the complexity of the minimum outer-connected dominating set problem in graphs
• Complexity of total outer-connected domination problem in graphs
• On the outer-connected domination in graphs
• On the number of outer connected dominating sets of graphs
• Approximation algorithms for connected dominating sets
• Approximation algorithms for connected dominating sets
• On the total outer-connected domination in graphs
• scientific article; zbMATH DE number 5823716
• Outer-\(k\)-connected component domination in graphs

Cited in

(17)

• Algorithmic aspects of secure connected domination in graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Complexity aspects of variants of independent Roman domination in graphs
• Weighted restrained domination in subclasses of planar graphs
• Finding outer-connected dominating sets in interval graphs
• Algorithmic aspects of total Roman \(\{3\}\)-domination in graphs
• Complexity issues of perfect secure domination in graphs
• Total vertex-edge domination in graphs: Complexity and algorithms
• Algorithmic aspects of outer independent Roman domination in graphs
• Algorithm and hardness results for outer-connected dominating set in graphs
• Algorithmic complexity of weakly connected Roman domination in graphs
• On the complexity of the minimum outer-connected dominating set problem in graphs
• Algorithmic aspects of total Roman ${2}$-domination in graphs
• Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs
• scientific article; zbMATH DE number 7693181 (Why is no real title available?)
• Total 2-rainbow domination in graphs: complexity and algorithms
• Complexity of total outer-connected domination problem in graphs

This page was built for publication: Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938747)