Abstract

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(n2) 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.