Abstract
以辭典編纂的次序產生所有最大獨立集合的意思是產生所有最大獨立集合，且按辭典編纂的次序來連續輸出最大獨立集合。對一般圖形而言，Johnson 教授在1988年提出了一個演算法，按辭典編纂的次序來產生所有最大獨立集合，且當一個最大獨立集合被找到並輸出後，下一個按次序的最大獨立集合能夠在多項的時間被找到並輸出。但此演算法需要指數的空間。所以 Johnson教授便提出了一個問題:是否能找到一個演算法完成上述的目的但只需要多項的空間？因此在此篇論文中，我們研究探討此問題並設法解決它。在我們提出解決 Johnson 教授問題的演算法中，主要依靠一個新問題一限制最大獨立集合問題。在一般圖形上，我們證明限制最大獨立集合此問題是 NP-Complete。然而，在樹圖形．區間圖形和弦圖形上，此問題各自能夠在 O(n)．O(nlogn) 和 O(n+m)的時間被解決；在此，n 和 m 各表示在圖形上端點和邊的數目。然後，根據解決限制最大獨立集合問題的演算法，我們提出了另一個演算法，在樹圖形，區間圖形和弦圖形上，按辭典編纂的次序來產生所有最大獨立集合，且當一個最大獨立集合被找到和輸出後，下一個按順序的最大獨立集合各自能夠在 O(n•n)，O(n•n+n•m) 和 O(n•n + n•m)的時間被找到並輸出。他們所需的空間皆為 O(n•n)。因此，我們部份地解決了 Johnson 教授所提的問題。除此之外，是否有一限制最大獨立集合包含某一特定的端點此決定問題，在樹圖形，區間圖形和弦圖形上，能各自先以 O(n)． O(nlogn) 和O(n+m)的先前處理時間，各在 O(1) 的時間解決。