Total domination in interval graphs (Q5903156)

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.