FAST ALGORITHMS FOR THE DOMINATING SET PROBLEM ON PERMUTATION GRAPHS

An O(n log log n) (resp. O(n2 log2 n)) algorithm is presented to solve the minimum cardinality (resp. weight) dominating set problem on perm utation graphs, assuming the input is a permutation. The best-known pr evious algorithm was given by Farber and Keil, where they use dynamic programming to get an O(n2) (resp. O(n3)) algorithm. Our improvement i s based on the following three factors: (1) an observation on the orde r among the intermediate terms in the dynamic programming, (2) a new c onstruction formula for the intermediate terms, and (3) efficient data structures for manipulating these terms.