Complexity of total outer-connected domination problem in graphs

DOI10.1016/J.DAM.2015.05.009MaRDI QIDQ896660zbMATH OpenOpenAlexFDO

Authors B. S. Panda, Arti Pandey

Publication date 10 December 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.05.009

zbMATH Keywords

graph algorithmsdominationNP-completechordal graphAPX-completetotal outer-connected domination

Mathematics Subject Classification ID

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

Recommendations

• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• Algorithm and hardness results for outer-connected dominating set in graphs
• On the complexity of the minimum outer-connected dominating set problem in graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• The outer-connected domination number of a graph

Cites work

• scientific article; zbMATH DE number 5823716 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• A note on the total outer-connected domination number of a tree
• A survey of selected recent results on total domination in graphs
• Algorithm and hardness results for outer-connected dominating set in graphs
• Algorithmic aspects of \(k\)-tuple total domination in graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Dually Chordal Graphs
• Graph theory
• Incidence matrices and interval graphs
• Inequality of Nordhaus-Gaddum type for total outer-connected domination in graphs
• On the complexity of the minimum outer-connected dominating set problem in graphs
• On the outer-connected domination in graphs
• On the total outer-connected domination in graphs
• Optimization, approximation, and complexity classes
• Some APX-completeness results for cubic graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The outer-connected domination number of a graph
• Total domination in graphs
• Total outer-connected domination in trees
• Total outer-connected domination numbers of trees

Cited in

(9)

• Algorithm and hardness results for outer-connected dominating set in graphs
• The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
• Outer-\(k\)-connected component domination in graphs
• On the computational complexity of upper total domination
• Computing a minimum outer-connected dominating set for the class of chordal graphs
• Complexity of Total {k}-Domination and Related Problems
• Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
• Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy
• On the complexity of the minimum outer-connected dominating set problem in graphs

This page was built for publication: Complexity of total outer-connected domination problem in graphs

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