跳到主要內容

臺灣博碩士論文加值系統

(216.73.216.47) 您好!臺灣時間:2026/05/21 18:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張儀興
研究生(外文):Yi-Hsing Chang
論文名稱:依辭典編纂的次序產生所有最大獨立集合
論文名稱(外文):A Study on Generating All Maximal Independent Sets in Lexicographic Order
指導教授:李家同,王家祥
指導教授(外文):R.C.T. Lee and J.S. Wang
學位類別:博士
校院名稱:國立清華大學
系所名稱:資訊科學學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1993
畢業學年度:81
語文別:中文
中文關鍵詞:辭典編纂的次序限制最大獨立集合樹圖形區間圖形弦圖形NP-完全
外文關鍵詞:Lexicographic ordertreesinterval graphschordal graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:224
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
  以辭典編纂的次序產生所有最大獨立集合的意思是產生所有最大獨立
集合,且按辭典編纂的次序來連續輸出最大獨立集合。對一般圖形而言,
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
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top