無序的樹收縮

Abstract

樹收縮(tree contraction)是經由一連串互不衝突的移走頂點以逐漸萎縮一有根樹(r ooted tree) 使其只剩下它的根。此方法可視為是針對樹上平行計算(parallel comp utations on trees)的一種一般性的排班技巧(Scheduling)。以前的研究主要是專注 在有序根樹 (ordered rooted tree)，例如：代數樹上求值，算式運算求值和cograp h上求最大完全子圖 (clique)等等問題，而我們在這篇文章中將討論無序根樹(unord ered rooted tree) 。我們將以串並聊網路(series-parallel network) 為例子來作 一說明何謂“無序的樹收縮”。 本文致力於找尋一串並聯網路上的最大獨立數(independent number)，通常一串並聯 網路可以由許多非同構的(nonisomorphic) 串並聯圖(series-parallel graph) 來表 示它，我們不可能一個個去計算串並聯圖的獨立數，然後再找其中的最大值。因此我 們首先介紹求串並聯網路上最大獨立數的一些特性。接著描述求此最大獨立數的一循 序線性演算法 (sequential Linear algorithm)，再將此線性演算法的特性與攫取自 樹收縮的精神，發展出一可以在同讀不同寫的平行計算機(CREW model)上使用n/logn 個處理器和O(logn) 時間內完成的平等演算法(parallel algorithm)。另外串並聯網 路上的一些問題，例如：最大配對數(maximum matching)，最小配對數(minimum mat ching)，加上最少的邊(edges) 使那些表示同一串並聯網路的非同構串並圖成為一尤 拉圖(Eulerian graph)等等，均可以在同樣的平行計算機上和同樣的處理器及時間內 ，用類似我們的平行演算法來解決。 最後，我們將此平行演算法加以推廣成可以解決許多無序根樹問題的一套方法，即我 們找出一些可以使用無序的樹收縮來解決問題的條件，只要是樹上的計算問題滿足了 我們的條件，我們均有興趣試著去解決它。