臺灣博碩士論文加值系統

　 以辭典編纂的次序產生所有最大獨立集合的意思是產生所有最大獨立
集合，且按辭典編纂的次序來連續輸出最大獨立集合。對一般圖形而言，
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) 的時間解決。

Contents
摘要
英文摘要
Chapter 1. Introduction
Chapter 2. The Constrained Maximal Independent Set Problem
Section 2.1 Definitions
Chapter 3. Solving the Constrained Maximal Independent Set Problem on Trees
Section 3.1 Solving the Constrained Maximal Independent Set Problem on Trees
Section 3.2 Finding the First Constrained Maximal Independent Set on Tree
Chapter 4. Solving the Constrained Maximal Independent Set Problem on Interval graphs
Section 4.1 Introduction
Section 4.2 Solving the Constrained Maximal Independent Set Problem on Interval Graphs
Chapter 5. Solving the Constrained Maximal Independent Set Problem on Chordal Graphs
Section 5.1 Introduction
Section 5.2 Solving the Constrained Maximal Independent Set Problem on Chordal Graphs
Chapter 6. Generating All Maximal Independent Sets in Lexicographic Orderon Trees, Interval and Chordal Graphs
Section 6.1 major Ideas
Section 6.2 The Algorithm GAMIS
Chapter 7. Concluding Remarks
References