Total domination in interval graphs (Q5903156)
From MaRDI portal
scientific article; zbMATH DE number 3957171
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Total domination in interval graphs |
scientific article; zbMATH DE number 3957171 |
Statements
Total domination in interval graphs (English)
0 references
1986
0 references
A set of vertices D is a total dominating set for a graph \(G=(V,E)\) if every vertex in V is adjacent to a vertex in D. An interval graph is the intersection graph of intervals of the real line. This paper presents an \(O(| V| +| E|)\) time algorithm for the problem of finding the minimum cardinality total dominating set in an interval graph.
0 references
total domination
0 references
linear algorithm
0 references
total dominating set
0 references
interval graph
0 references
