|
在區間圖形（interval graph）上求主宰集合的問題有許許多多的變型（variant）。我們在此研究其中的三個問題，分別是：最大重量的最精簡之主宰集合問題（maximum-weight minimal do minating set problem），最大重量的最精簡之獨立主宰集合問題（maximum-weight minimal independent dominating set problem），最大重量的最精簡之連通主宰集合問題（maximum-weight minimal dominating set problem）。我們將提出兩個運算法（algorithm），一個用來解最大重量的最精簡之主宰集合問題，另一個用來解最大重量的最精簡之連通主宰集合問題。此二個運算法的時間複雜度（time complexity）皆為O(lｅl lvl)，其中E與V分別是所給圖形的邊（edge）與頂點（vertex）所形成的集合。至於最大重量的最精簡之獨立主宰集合問題，我們發現一個別人提出用來解最小重量的最精簡之獨立主宰集合問題的運算法，可經由簡單的修正，即可用來解這問題；是故，我們僅提出定理來證明此問題可被那個修正過的運算法所解，而不另提出別的運算法。該修正過的運算法的時間複雜度與舊的相同，是為O(lEl+lVl)。
何謂一個區間圖形呢？給定一個圖形（graph）G(V,E)，我們稱G為一個區間圖形如果能找到一個一對一的對應，存在於V跟一個由數線上之區間（interval）所組成的集合，且使得圖形上任兩個頂點相連若其對應的兩個區間在數線上的交集不為空集合。
|