Algorithm and hardness results for outer-connected dominating set in graphs

DOI10.1007/978-3-319-04657-0_16MaRDI QIDQ5746254zbMATH OpenOpenAlexFDO

Authors B. S. Panda, Arti Pandey

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

APX-completenessdominationNP-completenessouter-connected domination

Mathematics Subject Classification ID

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)

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
• The outer-connected domination number of a graph
• Computing a minimum outer-connected dominating set for the class of chordal graphs

Cited in

(12)

• A greedy algorithm for the fault-tolerant outer-connected dominating set problem
• Algorithm and hardness results on hop domination in graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• Finding outer-connected dominating sets in interval graphs
• On the complexity of the outer-connected bondage and the outer-connected reinforcement problems
• The outer-connected domination number of a graph
• On the complexity of the minimum outer-connected dominating set problem in graphs
• The Outer-Paired Domination of Graphs
• Impact of diameter and convex ordering for Hamiltonicity and domination
• A closer look at Hamiltonicity and domination through the lens of diameter and convexity
• 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 Q5746254)