Connected domination and Steiner set on weighted permutation graphs (Q1190520)

Let \(G=(V,E)\) be an undirected graph and \(S\subseteq V\). \(S\) dominates \(G\) if every \(v\in V\) either belongs to \(S\) or is adjacent to some vertex of \(S\). \(S\) is a connected dominating set of \(G\) if \(S\) dominates \(G\) and the subgraph induced by \(S\) is connected. Let \(R\subseteq V\). A subset \(S\subseteq V\) is Steiner set with respect to \(R\) if \(S\) is a smallest set such that \(R\cup S\) is connected in \(G\). Finding a minimum connected dominating set and a minimum Steiner set are, in general, \(NP\)-complete problems, but, when the class of graphs is appropriately restricted, those problems have polynomial time algorithms. This paper focuses attention on the class of permutation graphs. The authors improve algorithms for minimum weight (respectively, minimum cardinality) connected dominating set for permutation graphs from \(O(n^ 3)\) (respectively, \(O(n^ 2)\)) to \(O(m+n\log n)\) (respectively, \(O(n+m)\)). They also improve algorithms for the minimum weight (respectively, minimum cardinality) Steiner subset from \(O(m^ 2)\) (respectively \(O(n^ 3)\) to \(O(m+n\log n)\)) (for both cases).