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

DOI10.1007/978-3-319-04657-0_16zbMath1408.68070OpenAlexW2254898045MaRDI QIDQ5746254

Arti Pandey, B. S. Panda

Publication date: 18 February 2014

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-04657-0_16

zbMATH Keywords

NP-completenessdominationouter-connected dominationAPX-completeness

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)

Related Items (3)

Complexity of total outer-connected domination problem in graphs ⋮ Finding outer-connected dominating sets in interval graphs ⋮ A greedy algorithm for the fault-tolerant outer-connected dominating set problem

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