各種圖類上的生成樹問題

Abstract

生成樹 (spanning tree) 問題在計算機科學上，不僅是演算法領域的一個重要課題，同時也具有許多實務上的應用。例如通訊網路設計、圖形編碼以及傳輸路徑設計。根據不同的應用需求，所產生的生成樹問題也不同。最為人所知的生成樹問題為最小成本生成樹 (minimum cost spanning tree) 以及最短路徑生成樹 (shortest path tree)。這兩個問題都是古典的生成樹問題，且均可在多項式時間內被解決。然而，並不是所有生成樹問題都是容易解決的。例如斯坦納最小成本樹(Steiner minimal tree) 以及最多葉生成樹 (maximum leaf spanning tree) 都是屬於NP-complete的問題。 我的論文─各種圖類上的生成樹問題，主要是研究局部連通生成樹 (locally connected spanning tree) 與度保留生成樹 (degree-preserving spanning tree)。這兩個生成樹問題已經被證明是 NP-complete。我的研究主要是在 directed path graph，strongly chordal graph 與 circular-arc graph 這三種不同的圖類 (graph class) 上設計多項式時間演算法。 局部連通生成樹問題是要在圖上找一棵生成樹，使得每一個點位於樹上的鄰居在原圖上所形成的誘導子圖 (induced subgraph) 會是連通的。在給定 strong elimination order 的情況下，我們在 strongly chordal graph 上提出一個 O(m+n)-time 演算法。在給定 intersection model 的情況下，我們在 circular-arc graph 上設計出一個 O(n)-time 演算法。以上這兩個演算法均可測定圖是否含有局部連通生成樹。如果有，我們將產生此局部連通生成樹。 度保留生成樹這一個問題是要在圖上找一棵生成樹具有最多的度保留點 (degree-preserving vertex)。對於一個點而言，如果它在圖上的鄰居與它在生成樹上的鄰居相同，則我們稱這個點具有度保留的性質。在給定 strong elimination order 及 tail order 的情況下，我們在 strongly chordal graph 及 directed path graph上分別提出 O(m α(m,n))-time 及 O(m+n)-time 演算法。在 intersection model 給定的情況下，我們在 circular-arc graph 上設計出 O(n^2)-time 演算法。以上這三個演算法均會產生度保留生成樹。

A spanning subgraph of a graph G is a subgraph containing all vertices of G. A spanning tree of G is a spanning subgraph of G that is a tree. Spanning trees are not only fundamental in algorithmic graph theory but also practically important in many applications such as communication networks, messages encoding and routing algorithm. Based on different criteria on spanning trees, there are different types of spanning trees. The most famous spanning tree problems are the minimum cost spanning tree problem and the shortest path tree problem. Both problems are solvable in polynomial time. On the other hand, some spanning tree problems are not easy to be solved. For example, the Steiner minimal tree problem and the maximum leaf spanning tree problem are NP-complete. In this dissertation, we study the problems of finding locally connected spanning trees and degree-preserving spanning trees. Both problems have been proven to be NP-complete on general graphs. We design polynomial-time algorithms for these two problems on some graph classes such as directed path graphs, strongly chordal graphs and circular-arc graphs. A locally connected spanning tree of a graph G is a spanning tree T such that the set of all neighbors of v in T induces a connected subgraph of G for every vertex v of G. Given a strong elimination order of a strongly chordal graph, we propose an O(m+n)-time algorithm for determining whether the graph contains a locally connected spanning tree and producing it if it exists. Further, given an intersection model of a circular-arc graph, an O(n)-time algorithm for finding locally connected spanning trees on circular-arc graphs are proposed. A vertex v of G is a degree-preserving vertex if its degree in T is the same as in G. The degree-preserving spanning tree problem is to find a spanning tree T of a connected graph G such that the number of degree-preserving vertices is maximum. Given a strong elimination order of a strongly chordal graph, we show an O(m α(m, n))-time algorithm on strongly chordal graphs, where α is the inverse of Ackermann's function. Moreover, given a tail order of a directed path graph, an O(m+n)-time algorithm for the degree-preserving spanning tree problem on directed path graphs is proposed. Further, given an intersection model of a circular-arc graph, we show an algorithm on circular-arc graphs that can be completed in O(n^2) time.