Computing a minimum outer-connected dominating set for the class of chordal graphs
From MaRDI portal
Publication:2444768
graph algorithmsouter-connected dominationdominationNP-completeproper interval graphundirected path graphdoubly chordal graph
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) 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
- Complexity of total outer-connected domination problem in graphs
- Finding outer-connected dominating sets in interval graphs
- On the complexity of the minimum outer-connected dominating set problem in graphs
- Algorithm and hardness results for outer-connected dominating set in graphs
- Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
Cites work
- scientific article; zbMATH DE number 5823716 (Why is no real title available?)
- scientific article; zbMATH DE number 4152428 (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 characterisation of rigid circuit graphs
- A linear time recognition algorithm for proper interval graphs
- A recognition algorithm for the intersection graphs of paths in trees
- Algorithmic aspects of \(k\)-tuple total domination in graphs
- Dominating Sets in Chordal Graphs
- Dominating sets for split and bipartite graphs
- Doubly chordal graphs, steiner trees, and connected domination
- Dually Chordal Graphs
- Graph Classes: A Survey
- Incidence matrices and interval graphs
- Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs
- On the complexity of signed and minus total domination in graphs
- On the outer-connected domination in graphs
- Representations of chordal graphs as subtrees of a tree
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The outer-connected domination number of a graph
- Variations of \(Y\)-dominating functions on graphs
- Variations of maximum-clique transversal sets on graphs
Cited in
(16)- On the complexity of the outer-connected bondage and the outer-connected reinforcement problems
- Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs
- Algorithm and hardness results for outer-connected dominating set in graphs
- A greedy algorithm for the fault-tolerant outer-connected dominating set problem
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
- The outer-connected domination number of Sierpiński-like graphs
- Bounds for the connected domination number of maximal outerplanar graphs
- Intersection graphs of non-crossing paths
- Finding outer-connected dominating sets in interval graphs
- scientific article; zbMATH DE number 4045183 (Why is no real title available?)
- Bisplit graphs -- a structural and algorithmic study
- Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy
- Complexity of total outer-connected domination problem in graphs
- On the complexity of the minimum outer-connected dominating set problem in graphs
- The Outer-Paired Domination of Graphs
This page was built for publication: Computing a minimum outer-connected dominating set for the class of chordal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2444768)
