An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
Chongkye Rhee, Y. Daniel Liang, Sudarshan Dhall, S. Lakshmivarahan · SIAM Journal on Computing · 1996
Farber and Keil [Algorithmica, 4 (1989), pp. 221–236] presented an $O(n^3 )$-time algorithm for finding a minimum-weight dominating set in permutation graphs. This result was improved to $O(n^2 \log ^2 n)$ by Tsai and Hsu [SIGAL ’90 Algorithms, Lecture Notes in Computer Science, Springer-Verlag, New York, 1990, pp. 109–117] and to $O(n(n + m)$ by the authors of this paper [Inform. Process. Lett., 37 (1991), pp. 219–224], respectively. In this paper, we introduce a new faster algorithm that takes only $O(n + m)$ time to solve the same problem, where m is the number of edges in a graph of n vertices.