Finding a minimum independent dominating set in a permutation graph (Q1117255)

1985, \textit{M. Farber} and \textit{J. M. Keil} published a paper with the title `Domination in permutation graphs' in J. Algorithms 6, 309-321 (1985; Zbl 0598.05056), where they studied the problem of finding a minimum independent dominating set in a permutation graph and where they presented an \(O(n^ 3)\)-time algorithm. The three authors of this paper study the same problem and succeed in giving an O(n \(log^ 2 n)\)-time algorithm by means of a linear time reduction from the problem of finding a minimum independent dominating set (MIDS) to the problem of computing a shortest maximal increasing subsequence (SMIS).