A total dominating set of a graph G is a subset S of nodes such that each node of G is adjacent to some node of S. We present an \(O(n^ 2)\) time algorithm for finding a minimum cardinality total dominating set in an interval graph (one which represents intersecting intervals on the line) by reducing it to a shortest path problem on an appropriate acyclic directed network.
Recommendations
Cites work
- Dominating sets for split and bipartite graphs
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3706451 (Why is no real title available?)
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3596896 (Why is no real title available?)
- On the Algorithmic Complexity of Total Domination
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- The NP-completeness column: An ongoing guide
- Total domination in graphs
Cited in
(30)- On the domatic number of interval graphs
- A unified approach to domination problems on interval graphs
- Total domination in interval graphs revisited
- Total domination in block graphs
- Dominating sets in perfect graphs
- On minimum intersection of two minimum dominating sets of interval graphs
- Minimum dominating sets of intervals on lines
- On the computational complexity of upper total domination
- The bottleneck independent domination on the classes of bipartite graphs and block graphs.
- Achromatic number is NP-complete for cographs and interval graphs
- Weighted independent perfect domination on cocomparability graphs
- Hardness results and approximation algorithm for total liar's domination in graphs
- Total 2-domination of proper interval graphs
- New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
- The harmonious coloring problem is NP-complete for interval and permutation graphs
- Total domination and transformation
- Total domination in circular-arc graphs
- Total Domination and Irredundance in Weighted Interval Graphs
- Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
- Finding outer-connected dominating sets in interval graphs
- Total Roman domination for proper interval graphs
- Counting dominating sets in generalized series-parallel graphs
- Parallel algorithms on circular-arc graphs
- Total domination in interval graphs
- Minimum dominating sets of intervals on lines
- Convexity of minimal total dominating functions in graphs
- On total traffic domination in non-complete graphs
- Bibliography on domination in graphs and some basic definitions of domination parameters
- New sequential and parallel algorithms for interval graph recognition
- A survey of selected recent results on total domination in graphs
This page was built for publication: Total domination in interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5903263)
