Computing a minimum outer-connected dominating set for the class of chordal graphs
From MaRDI portal
Publication:2444768
dominationdoubly chordal graphgraph algorithmsNP-completeouter-connected dominationproper interval graphundirected path graph
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) Graph theory (including graph drawing) in computer science (68R10)
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
- 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 for split and bipartite graphs
- Dominating Sets in Chordal Graphs
- Doubly chordal graphs, steiner trees, and connected domination
- Dually Chordal Graphs
- Graph Classes: A Survey
- 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?)
- 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)- A greedy algorithm for the fault-tolerant outer-connected dominating set problem
- Bounds for the connected domination number of maximal outerplanar graphs
- The outer-connected domination number of Sierpiński-like graphs
- Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy
- Enumerating minimal connected dominating sets in graphs of bounded chordality
- scientific article; zbMATH DE number 4045183 (Why is no real title available?)
- Finding outer-connected dominating sets in interval graphs
- A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs
- On the complexity of the outer-connected bondage and the outer-connected reinforcement problems
- Algorithm and hardness results for outer-connected dominating set in graphs
- On the complexity of the minimum outer-connected dominating set problem in graphs
- Intersection graphs of non-crossing paths
- The Outer-Paired Domination of Graphs
- Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs
- Bisplit graphs -- a structural and algorithmic study
- Complexity of total outer-connected domination problem in 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)
