圓形圖上的支配相關問題

Abstract

支配問題是圖論中一個研究已久的重要領域，並且在多個圖類中已有相關研究。本論文聚焦於圓形圖及其兩個子類別：k-多邊形圖和保距圖，我們為解決這些圖類中的支配問題提供了新的見解和成果。

在圓形圖的研究中，我們透過將該問題歸約到漢密頓路徑問題，證明了成對支配問題的NP完全性。此外，我們設計了一個O(n+m)時間的演算法來計算圓形圖的最小葉區覆蓋。在Damian和Pemmaraju的成果基礎上，我們擴展了其應用，設計了針對完全支配問題的10倍近似演算法和成對支配問題的12倍近似演算法。接著我們更進一步為完全支配和成對支配問題分別提出了(2+ε)和(4+ε)的近似演算法。

對於k-多邊形圖，我們提出了多項式時間解決支配、完全支配和成對支配問題的演算法。我們設計了一個高效的O(n^(3k-5))時間複雜度的演算法來解決支配和完全支配問題，以及一個O(n(n/(k^2-k))^(2k^2-2k))時間複雜度的演算法來解決成對支配問題。

在保距圖的研究中，我們提出了一個O(n+m)時間的演算法來尋找最小成對支配集，並在已知分解樹的情況下將其時間複雜度降低至O(n)。我們的方法基於動態規劃，通過在分解樹上自下而上的計算關鍵值，並利用建立新的數學關係式使得計算過程更加高效。

總的來說，本論文貢獻了創新的演算法和理論結果，推動了圓形圖及其子類上支配相關問題的研究，為未來相關領域的研究提供了有價值的工具。

The domination problems across specific classes of graphs are an important topic in graph theory and have been studied in various graph classes. This thesis focuses on circle graphs and two of their subclasses: k-polygon graphs and distance-hereditary graphs. Through innovative approaches and efficient algorithm designs, we contribute new insights and results for addressing domination-related issues in these graph classes.

In the case of circle graphs, we establish the NP-completeness of the paired-domination problem through a reduction from the Hamiltonian path problem. Additionally, we design an O(n+m)-time algorithm to compute a minimum leaf sector cover on circle graphs. Building upon prior work, we extend the leaf sector cover to develop 10-approximation and 12-approximation algorithms for the total domination and paired-domination problems, respectively. Then, we further propose (2+ε)- and (4+ε)-approximation schemes for these problems.

For k-polygon graphs, we present polynomial-time algorithms to solve the domination, total domination, and paired-domination problems. These results are refined with a more efficient O(n^(3k-5))-time algorithm for the domination and total problem, and an O(n(n/(k^2-k))^(2k^2-2k))-time algorithm for paired-domination.

In the realm of distance-hereditary graphs, we improve the efficiency of finding minimum paired-dominating sets by given an O(n+m)-time algorithm, which can be reduced to O(n) when a decomposition tree is available. Our approach, based on dynamic programming, computes key values on the decomposition tree in a bottom-up manner by establishing new mathematical equations that streamline the computation process.

Overall, this thesis contributes novel algorithms and theoretical results that advance the study of domination-related problems on circle graphs and its subcalsses, offering valuable tools for future research in this area.