Total domination in interval graphs (Q5903263)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Total domination in interval graphs |
scientific article; zbMATH DE number 3974991
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| 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
0.9751251339912416
0 references
0.898427426815033
0 references
0.8810933828353882
0 references
0.8809008002281189
0 references
0.8793140053749084
0 references
