Total domination in interval graphs (Q5903263)
From MaRDI portal
scientific article; zbMATH DE number 3974991
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Total domination in interval graphs |
scientific article; zbMATH DE number 3974991 |
Statements
Total domination in interval graphs (English)
0 references
1986
0 references
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.
0 references
polynomial-time algorithm
0 references
total dominating set
0 references
interval graph
0 references
shortest path problem
0 references
acyclic directed network
0 references
0 references
