Total Domination and Irredundance in Weighted Interval Graphs
Alan A. Bertossi, Alessandro Gori · SIAM Journal on Discrete Mathematics · 1988
In an undirected graph, a subset X of the nodes is a total dominating set if each node in the graph is a neighbor of some node in X. In contrast, X is an irredundant set if the closed neighborhood of each node in X is not contained in the union of closed neighborhoods of the other nodes in X. This paper gives $O( n\log n )$ and $O( n^4 )$ time algorithms for finding, respectively, a minimum weighted total dominating set and a minimum weighted maximal irredundant set in a weighted interval graph, i.e., one that represents n intersecting intervals on the real line, each having a (possibly negative) real weight.