Connected domination and Steiner set on weighted permutation graphs

O(m +n log n) algorithms are presented for the minimum-weight connected dominating set and minimum-weight Steiner subset of a permutation graph. If the graph is unweighted, a minimum-cardinality connected dominating set can be found in O(m + n) time. © 1992.