AN O(N+M)-TIME ALGORITHM FOR FINDING A MINIMUM-WEIGHT DOMINATING SET IN A PERMUTATION GRAPH

摘要

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 + rn) time to solve the same problem, where m is the number of edges in a graph of n vertices. [References: 12]