圈結構及其算法研究

《圈結構及其算法研究》是依託香港理工大學深圳研究院，由操宜新擔任項目負責人的面上項目。

基本介紹

• 中文名：圈結構及其算法研究
• 項目類別：面上項目
• 項目負責人：操宜新
• 依託單位：香港理工大學深圳研究院

項目摘要

圈是圖論中最古老也最重要的結構之一，圍繞它的算法問題一直是圖算法領域的核心課題之一，而這些算法都依賴於對圈的組合理解。我們第一個重點關注的問題是頂點反饋集問題，這個問題在有向圖和無向圖中都是NP難的。我們計畫提出更有效的固定參數算法。完美圖理論及其它各種套用中關注一種特殊的圈，就是三角形之外其它導出子圈（induced cycles），又叫做洞。沒有洞的圖叫做弦圖。我們的另一個關注點就是弦圖的修改問題，也就是說，如果通過最少的修改將一個給定圖變成弦圖。這個也是NP難的。此外，我們還將研究多項式時間可解的最短洞檢測和最短偶長度洞的檢測。

結題摘要

在本基金的支持下，課題組對圈結果和其算法套用進行了深入的研究，並且取得了很大進展。在無圈圖有關的算法設計方面，通過對森林和樹結構的深入分析，我們用最簡單的貪心和局部搜尋方法，得到了一系列突破性的結果，包括頂點反饋集、最大內部節點生成子樹。我們對無洞圖，也就是著名的弦圖上解決了若干著名的開放問題，包括區間圖的圖修改問題、單位區間圖的圖修改問題、弦圖子類之間的點刪除問題，以及稀疏矩陣運算中著名的最小填充問題。我們還在有關的問題上得到了一系列的核心化結果，這些成果在國際上有很大的影響。此外，此項目的研究對圖算法未來的發展起到了推動作用。