在置換生成圖中尋找最小的 k 距支配集

Abstract

給定一個置換π代表置換生成圖G，我們用O(n log n)時間與O(n)空間的演算法找到最小k距支配集。我們先找到一個動態規劃的規則，再參考Farber與Keil在同類型的圖上對於支配集(即k = 1的情況)的動態規劃演算法，將兩者合併後變成O(n^2)時間演算法，最後引入AVL樹，改良成O(n log n)時間演算法。

Given a permutation π which denotes a permutation graph G. We use an O(n log n) time and O(n) space algorithm to find a minimum distance-k dominating set. We first find a dynamic programming rule, then we combine it with another dynamic programming algorithm given by Ferber and Keil, which is used to find minimum dominating set (the case of k = 1) on permutation graphs. So the O(n2) time algorithm is created. Finally, we use AVL tree to reduce our time complexity to O(n log n).