K-獨立集問題

Abstract

若圖形Ｇ＝（Ｖ，Ｅ）且ｋ是一固定正整數時，則一個圖形Ｇ的ｋ－獨立集Ⅰ，就是 Ｖ的一個部份集合，使得此部份集合Ⅰ中的任意相異兩點在Ｇ中的距離（DISTANCE） 均大於ｋ。ｋ－獨立集問題（K-INDEPENDENT SET PROBLEM ）就是希望能找出Ｇ中具 有最多元素個數的ｋ－獨立集。本論文主要的目的就是從演算法（ALGORITHM ）的角 度來研究ｋ－獨立集問題。 張鎮華教授及G.L.NEMHAUSER 先生曾提出Ｏ（ｎ3 ）時間的演算法來解決當ｋ是偶數 時的無日弦圖（SUN-FREE CHORDAL GRAPH）的ｋ一獨立集問題。同時A. LUBIW先生證 明了無日弦圖的整數次方仍是無日弦圖，A. RAYCHAUDHURT 先生也證明了圓弧圖（CI RCULAR ARCGRAPH ）的整數次方仍是圓弧圖，並提出Ｏ（ｎ3 ）時間的演算法以解決 圓弧圖的ｋ一獨立集問題。以上的演算法都是經由建構Ｇ的ｋ次方圖形，然後利用已 知的１－獨立集演算法。 本論文則捨棄使用建構Ｇ的ｋ次方圖形方法，而分別對區間圖（INTERVAL GRAPH）， 圓弧圖及無日弦圖提出Ｏ（N LOG N ），Ｏ（N LOG N+KN）及（｜Ｅ｜＋｜Ｖ｜）時 間的演算法來解ｋ一獨立集問題。而且若區域間圖，圓弧圖是正規的（canonical ） 時，演算法則分別僅需Ｏ（ｎ）及Ｏ（kn）時間。如此本論文所提的演算法，降低了 ｋ一獨立集問題在區間圖，圓弧圖及無日弦圖上的演算法的時間複雜度（TIME COMPL EXITY ）。