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

DOI10.7155/jgaa.00334zbMath1305.05179OpenAlexW2060834235MaRDI QIDQ2938747

B. S. Panda, Arti Pandey

Publication date: 15 January 2015

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

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

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) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (11)

Complexity issues of perfect secure domination in graphs ⋮ Weighted restrained domination in subclasses of planar graphs ⋮ Total vertex-edge domination in graphs: Complexity and algorithms ⋮ Complexity aspects of variants of independent Roman domination in graphs ⋮ Algorithmic aspects of outer independent Roman domination in graphs ⋮ Algorithmic Aspects of Outer-Independent Total Roman Domination in Graphs ⋮ Unnamed Item ⋮ Algorithmic aspects of total Roman ${2}$-domination in graphs ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ Algorithmic complexity of weakly connected Roman domination in graphs ⋮ Algorithmic aspects of total Roman {3}-domination in graphs

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