1、圖的控制數(shù)理論是圖論中一個重要的研究領(lǐng)域，它在計算機科學(xué)，通訊科學(xué)，網(wǎng)絡(luò)理論，電力系統(tǒng)，社會學(xué)，特別是在計算機網(wǎng)絡(luò)和通訊系統(tǒng)研究中有著廣泛應(yīng)用。我們稱點集S()V為圖G=(V,E)的控制集如果對任意的點v∈V-S，總存在S中的一個點與v鄰接。圖G的控制數(shù)γ(G)是圖G的控制集的最小基數(shù)。在圖的控制數(shù)理論研究中，算法復(fù)雜性研究是一個十分活躍的研究方向，其中一項重要工作是在特殊圖類上尋找控制數(shù)及其相關(guān)參數(shù)的有效算法。區(qū)間圖是一類著名的特殊圖

2、類，它形成弦圖和完美圖的子類，它們在解決很多現(xiàn)實問題中有重要作用。由于區(qū)間圖具有良好的結(jié)構(gòu)性質(zhì)，因此許多NP-完全的控制數(shù)及其相關(guān)參數(shù)問題限制在區(qū)間圖上都是多項式時間可解的。本文主要研究了兩類控制參數(shù)在區(qū)間圖上的算法問題，分為兩個部分。 第一部分：研究了直線簇上區(qū)間圖的最小獨立控制集和最小連通控制集的求解問題。人們已經(jīng)證明：許多控制相關(guān)參數(shù)如獨立控制數(shù)，連通控制數(shù)，全控制數(shù)的求解問題，當(dāng)限制在一條直線上區(qū)間圖時，基本上都有線性時

3、間算法。本文研究了廣義區(qū)間圖的情況，即多條直線上(直線簇)的區(qū)間圖的最小獨立控制集和最小連通控制集的求解問題。對給定的直線簇上區(qū)間圖的兩個模型，分別給出了求解上述兩類問題的多項式時間算法。 第二部分：研究了包含賦權(quán)點的區(qū)間圖的最小獨立控制集和最小連通控制集的求解問題。對一條直線上的區(qū)間圖，其上有n個區(qū)間和t個賦權(quán)點，要找此區(qū)間圖的最小獨立控制集(最小連通控制集)，使得其覆蓋的點權(quán)和最大。利用動態(tài)規(guī)劃方法，給出了求解此區(qū)間圖的最大