Total domination in interval graphs (Q5903156): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(86)90022-0 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2062262038 / rank | |||
Normal rank |
Revision as of 22:16, 19 March 2024
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