Abstract
本篇論文討論了一些分散式圖形問題, 如切割點問題, 雙連接問題, 以及三個支配集問題。我們提出了解決這些問題之有效的演算法。此外, 我們還發展了一個設計集中式演算法的統合性方法。對於切割點問題, 我們提出一個半集中式的分演式演算法, 此演算法總共送了0(e)個訊息。對於雙連接的問題, 我們也提出了一個半集中式的分散式演算法, 此演算法總共送了0(e+mn) 個訊息。這裹m 代表在所有切割點中最大的區域度。然後我們討論了三個支配集問題, 包括最小支配集問題, 最小完全支配集問題, 以及最小連接支配集問題。對最小支配集問題和最小完全支配集問題, 我們分別發展了集中式以及非集中式的分散式演算法, 並且我們證明了這四個演算法有相同的訊息複雜度0(e)。對最小連接支配集問題, 我們提出了一個花費0(n*n)個訊息的集中式演算法。最後, 我們找出了一個以上這些集中式或半集中式演算法的共同特性, 依據這個特性我們發展了一個設計集中式或半集中演算法的統合性方法。我們也將前人發展的演算法和利用此方法所設計的演算法做了比較, 我們的演算法的訊息複雜度優於或相等於前人發展的演算法。