標題: K-獨立集問題
作者: 盧冬琳
LU, DONG-LIN
張鎮華
ZHANG, ZHEN-HUA
應用數學系所
關鍵字: K-獨立集;無日弦圖;圓弧圖;區間圖;時間複雜度;K-INDEPENDENT-SET;G.L.-NEMHAUSER;SUN-FREE-CHORDAL-GRAPH;A.LUBIW;A.RAYCHAUDHURT;CIRCULAR-ARC-GRAPH;INTERVAL-GRAPH;TIME-COMPLEXITY
公開日期: 1988
摘要: 若圖形G=(V,E)且k是一固定正整數時,則一個圖形G的k-獨立集Ⅰ,就是 V的一個部份集合,使得此部份集合Ⅰ中的任意相異兩點在G中的距離(DISTANCE) 均大於k。k-獨立集問題(K-INDEPENDENT SET PROBLEM )就是希望能找出G中具 有最多元素個數的k-獨立集。本論文主要的目的就是從演算法(ALGORITHM )的角 度來研究k-獨立集問題。 張鎮華教授及G.L.NEMHAUSER 先生曾提出O(n3 )時間的演算法來解決當k是偶數 時的無日弦圖(SUN-FREE CHORDAL GRAPH)的k一獨立集問題。同時A. LUBIW先生證 明了無日弦圖的整數次方仍是無日弦圖,A. RAYCHAUDHURT 先生也證明了圓弧圖(CI RCULAR ARCGRAPH )的整數次方仍是圓弧圖,並提出O(n3 )時間的演算法以解決 圓弧圖的k一獨立集問題。以上的演算法都是經由建構G的k次方圖形,然後利用已 知的1-獨立集演算法。 本論文則捨棄使用建構G的k次方圖形方法,而分別對區間圖(INTERVAL GRAPH), 圓弧圖及無日弦圖提出O(N LOG N ),O(N LOG N+KN)及(|E|+|V|)時 間的演算法來解k一獨立集問題。而且若區域間圖,圓弧圖是正規的(canonical ) 時,演算法則分別僅需O(n)及O(kn)時間。如此本論文所提的演算法,降低了 k一獨立集問題在區間圖,圓弧圖及無日弦圖上的演算法的時間複雜度(TIME COMPL EXITY )。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT772507003
http://hdl.handle.net/11536/54167
Appears in Collections:Thesis