Full metadata record
DC FieldValueLanguage
dc.contributor.author盧冬琳en_US
dc.contributor.authorLU, DONG-LINen_US
dc.contributor.author張鎮華en_US
dc.contributor.authorZHANG, ZHEN-HUAen_US
dc.date.accessioned2014-12-12T02:06:12Z-
dc.date.available2014-12-12T02:06:12Z-
dc.date.issued1988en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#NT772507003en_US
dc.identifier.urihttp://hdl.handle.net/11536/54167-
dc.description.abstract若圖形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 )。zh_TW
dc.language.isozh_TWen_US
dc.subjectK-獨立集zh_TW
dc.subject無日弦圖zh_TW
dc.subject圓弧圖zh_TW
dc.subject區間圖zh_TW
dc.subject時間複雜度zh_TW
dc.subjectK-INDEPENDENT-SETen_US
dc.subjectG.L.-NEMHAUSERen_US
dc.subjectSUN-FREE-CHORDAL-GRAPHen_US
dc.subjectA.LUBIWen_US
dc.subjectA.RAYCHAUDHURTen_US
dc.subjectCIRCULAR-ARC-GRAPHen_US
dc.subjectINTERVAL-GRAPHen_US
dc.subjectTIME-COMPLEXITYen_US
dc.titleK-獨立集問題zh_TW
dc.typeThesisen_US
dc.contributor.department應用數學系所zh_TW
Appears in Collections:Thesis