The complexity of connected dominating sets and total dominating sets with specified induced subgraphs
From MaRDI portal
Publication:1941700
DOI10.1016/j.ipl.2012.09.002zbMath1259.68084MaRDI QIDQ1941700
Oliver Schaudt, Rainer Schrader
Publication date: 21 March 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2012.09.002
computational complexity; combinatorial problems; total domination; connected domination; dominating subgraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Acyclic total dominating sets in cubic graphs, Linear separation of connected dominating sets in graphs, An efficient algorithm for distance total domination in block graphs, A unified greedy approximation for several dominating set problems, On a class of graphs between threshold and total domishold graphs, On dominating sets whose induced subgraphs have a bounded diameter, Connected Domination
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on connected dominating sets of distance-hereditary graphs
- Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
- Complete description of forbidden subgraphs in the structural domination problem
- Threshold dominating cliques in random graphs and interval routing
- Dominating cliques in \(P_ 5\)-free graphs
- Acyclic domination
- Restricted total domination in graphs
- An exact algorithm for the minimum dominating clique problem
- Dominating and large induced trees in regular graphs
- Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
- Planar 3DM is NP-complete
- Graph Classes: A Survey
- Hereditary domination and independence parameters
- Dominating cliques in graphs