Efficient domination on permutation graphs and trapezoid graphs

The weighted efficient domination problem was solved in O(nm) time for cocomparability graphs [6]. This paper investigates whether more efficient algorithms can be found for permutation graphs and trapezoid graphs - subclasses of cocomparability graphs. Specifically, we present an O(n + m) algorithm for the weighted efficient domination problem on permutation graphs and an O(n log log n + m) algorithm on trapezoid graphs, where m denotes the number of edges in the complement of G.