《參數計算中樹分解方法及其套用研究》是依託中南大學，由馮啟龍擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：參數計算中樹分解方法及其套用研究
- 項目類別：青年科學基金項目
- 項目負責人：馮啟龍
- 依託單位：中南大學
項目摘要,結題摘要,
項目摘要
作為有效求解難解問題的手段，樹分解方法受到了人們廣泛的關注。各領域中的諸多難解問題基於樹分解技術得到有效求解，如機率網路、生物信息學等。樹分解方法逐步成為人們研究的熱點，但樹分解許多方向的研究正處於起步階段，都待進一步發展和完善。. 本項目將樹分解方法進行深入研究，首先研究樹分解求解算法，以提高求解樹分解的效率。然後直接面向各領域的具體問題，研究樹分解與其它參數算法技術的結合套用，並基於此，從樹分解規約技術角度研究新的求解難解問題的方法。最後，以生物信息學為實際套用領域，研究樹分解在生物信息學難解問題求解中的套用。本項目的研究旨在建立系統的套用樹分解求解難解問題的方法，為套用領域中的難解問題求解提供新的思路，提高問題的求解效率，繼而推動相關套用領域的發展。
結題摘要
在本課題基金的支持下，按照研究計畫中的研究內容和技術路線進行了三年的研究工作，取得了較好的研究成果。綜合三年來的工作，在本基金的資助下，我們在主要研究了樹分解技術的套用，樹結構相關問題的參數算法和核心化，以及若干難解問題的參數算法和核心化研究，並把樹分解理論及其參數計算理論套用於計算機網路、社會學和生物信息學中。對樹分解及樹狀結構的參數算法研究中，本項目主要研究了基於樹分解的符號支配集問題參數算法、直角線段的路徑覆蓋問題、最大一致森林問題的參數算法、路徑覆蓋和星形覆蓋一棵樹問題和最大內部節點生成樹近似算法。對樹分解的符號支配集問題給出時間複雜度為O(k^k0.5)參數算法,對直角線段覆蓋問題給出大小為O((2d)k)的核及二維上時間複雜度為O(3k)的參數算法，對最大一致森林問題分別為有根和無根的多顆二叉樹給出時間複雜度為O(3k)和O(4k)的算法，對於路徑覆蓋和星形覆蓋問題，分別給出時間複雜度為O((2+c)k)和O(4k)的參數算法，其中星形覆蓋的核為O(k3)，最後對於最大內部節點生成樹，給出近似比為1.5的近似算法。項目對其他一些NP難解問題的核心化及參數算法也進行了研究，為它們提出來若干有效的歸約規則和高效的參數算法，例如加權的3-set Packing、正負支配集和 P2-packing等問題都給出了不錯的結果。對於加權的3-set Packing給出了O(k3)的核，對正負支配集問題給出一個亞指數的算法，以及P2-packing問題大小為O(k2)的核和O(8k)的參數算法。最後項目將參數計算推廣到實際套用中，取得了一系類成果。其中項目主要針對感測器網路和社交網路中的參數套用進行了研究，如無線感測器網路的Max- lifetime Target Coverage問題以及d-approval規則投票系統等問題。項目為其建立模型，設計近似算法，參數算法以及隨機算法。對Max- lifetime Target Coverage問題，項目證明Max-min Target Coverage是FPT的，而對d-approval規則投票系統問題，項目給出大小為O(kd+2)的核。 此項目的研究不僅對參數理論未來的發展起到極大的促進作用，同時也推動了用參數計算理論來求解實際問題的步伐
