請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/7464
標題: | 樹苗偵測演算法 Sapling Detection |
作者: | Kai-Yuan Lai 賴開元 |
指導教授: | 呂學一(Hsueh-I Lu) |
關鍵字: | 圖論,演算法, graph theory,algorithm, |
出版年 : | 2018 |
學位: | 碩士 |
摘要: | 偵測一個圖中是否含有某種特殊結構作為導出子圖是一個重要且被廣泛研究的問題,目前已經有許多結構已經被證明出其偵測屬於NP-complete類別。而有一些結構存在多項式時間演算法,我們研究其中關於樹苗的特例,並給出一個三次方時間的演算法,改進了先前最佳的四次方時間演算法。 The problem of determining whether a graph contains certain structure as induced subgraph has been extensively studied. Many of them have been shown belong to the complexity NP-complete. We study a special case regarding saplings and show an algorithm that solves the problem in cubic time, which is an improvement over the current best quadruple time algorithm. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/7464 |
DOI: | 10.6342/NTU201803034 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-107-1.pdf | 2.24 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。