scientific article; zbMATH DE number 1302196
From MaRDI portal
Publication:4247463
The purpose of the paper is to survey the algorithmic results of the domination problem in graphs. Section 2 gives definitions of classes of graphs - trees, interval graphs ect. Section 3 investigates different algorithms for domination in trees - labeling method, dynamic programming, primal-dual approach. Section 4 is for domination in interval graphs, section 5 surveys NP-complete results, and sections 6-9 are for classes of graphs in which the domination problem is solvable. For the entire collection see [Zbl 0914.90002].
Recommendations
Cited in
(68)- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- \(k\)-tuple domination in graphs
- Hardness results and approximation algorithms of \(k\)-tuple domination in graphs
- Hardness results and approximation algorithms for (weighted) paired-domination in graphs
- Distance paired-domination problems on subclasses of chordal graphs
- Labeling algorithms for domination problems in sun-free chordal graphs
- Algorithmic aspects of majority domination
- Perfect edge domination and efficient edge domination in graphs
- Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs
- Algorithmic aspect of k-tuple domination in graphs.
- The weighted independent domination problem is NP-complete for chordal graphs
- Power domination in circular-arc graphs
- Paired-domination problem on distance-hereditary graphs
- Algorithmic aspects of upper edge domination
- An \(O(n+m)\) time algorithm for computing a minimum semitotal dominating set in an interval graph
- A linear-time algorithm for weighted paired-domination on block graphs
- Partitioning vertices into in- and out-dominating sets in digraphs
- The k-power domination problem in weighted trees
- A linear-time algorithm for paired-domination on circular-arc graphs
- On the independent dominating set polytope
- On the dominating set polytope
- Generalized perfect domination in graphs
- Algorithmic aspect of stratified domination in graphs
- Rainbow domination and related problems on strongly chordal graphs
- Algorithmic aspects of the \(k\)-domination problem in graphs
- The algorithmic complexity of bondage and reinforcement problems in bipartite graphs
- Power domination in graphs
- Unsolved algorithmic problems on trees
- Minimum 2-tuple dominating set of permutation graphs
- Some advances on the set covering polyhedron of circulant matrices
- On dominating set polyhedra of circular interval graphs
- On the algorithmic complexity of edge total domination
- scientific article; zbMATH DE number 5010630 (Why is no real title available?)
- Perfect secret sharing scheme based on vertex domination set
- scientific article; zbMATH DE number 6531253 (Why is no real title available?)
- scientific article; zbMATH DE number 3918387 (Why is no real title available?)
- scientific article; zbMATH DE number 3974289 (Why is no real title available?)
- A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
- On the algorithmic complexity of \(k\)-tuple total domination
- k-rainbow domatic numbers
- scientific article; zbMATH DE number 1735803 (Why is no real title available?)
- scientific article; zbMATH DE number 1124601 (Why is no real title available?)
- NP-completeness and APX-completeness of restrained domination in graphs
- Generalized power domination of graphs
- Using genetic algorithm for the discrete domination over time problem
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
- An efficient algorithm to solve the distance \(k\)-domination problem on permutation graphs
- ON SOME NEW GRACEFUL GRAPHS
- The algorithmic complexity of mixed domination in graphs
- Algorithmic aspects of total k-subdomination in graphs
- Fundamentals of Computation Theory
- Domination in distance-hereditary graphs
- An efficient algorithm for distance total domination in block graphs
- Power domination with bounded time constraints
- \(k\)-power domination in block graphs
- Algorithmic aspects of paired disjunctive domination in graphs
- Towards a new framework for domination
- Leaf sector covers with applications on circle graphs
- Edge-vertex domination on interval graphs
- Minimum 2-tuple dominating set of an interval graph
- Computation of minimum d-hop connected dominating set of trees in O(n) time
- Minimum vertex-edge dominating set of permutation graphs
- On the \({k}\)-power domination of hypergraphs
- The upper bound on \(k\)-tuple domination numbers of graphs
- Variations of \(Y\)-dominating functions on graphs
- Rainbow domination on trees
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247463)
