Abstract
在串並圖上，很多組合問題都已經有了很好的演算法來解決，儘管如此，卻仍然還存有許多著名問題沒被解決。本篇論文中，我們分別針對三個問題提出對應的線性演算法來解決它。這三個問題分別是單一步驟搜尋問題、限制最大獨立集合問題和反饋頂點集合問題。一個串並圖能被分解成兩個較小的串並圖，此種遞迴關係可以用一棵分析樹來表示。我們發展出一些計算公式，根據分析樹上表示的遞迴關係，利用動態規劃法，由最小串並圖中的解來算出原始串並圖的解。這三個演算法都是在線性時間內可以找到最佳解。
- Title
- 利用動態規劃法解決一些串並圖上的問題
- Translated title
- 利用動態規劃法解決一些串並圖上的問題
- Creators
- 林明峰 (Author)
- Contributors
- 唐傳義 (Advisor)
- Awarding Institution
- National Tsing Hua University; Masters
- Theses and Dissertations
- Masters, National Tsing Hua University
- Resource Type
- Thesis
- Language
- English