Locally Connected Spanning Trees on Graphs

View Statistics Email Alert RSS Feed

Information

Details

Project title

Code/計畫編號

NSC97-2218-E019-005

Translated Name/計畫中文名

區域連通生成樹問題

Project Coordinator/計畫主持人

Ching-Chi Lin

Funding Organization/主管機關

National Science and Technology Council

Department/Unit

Department of Computer Science and Engineering

Website

https://www.grb.gov.tw/search/planDetail?id=1721106

Year

2008

Start date/計畫起

01-11-2008

Expected Completion/計畫迄

31-07-2009

Bugetid/研究經費

485千元

ResearchField/研究領域

資訊工程--硬體工程

生成樹 (spanning tree) 問題在計算機科學上，不僅是演算法領域的一個重要課題，同時也具有許多實務上的應用。例如通訊網路設計、圖形編碼以及傳輸路徑設計。根據不同的應用需求，所產生的生成樹問題也不同。最為人所知的生成樹問題為最小成本生成樹 (minimum cost spanning tree) 以及最短路徑生成樹 (shortest path tree)。這兩個問題都是古典的生成樹問題，且均可在多項式時間內被解決。然而，並不是所有生成樹問題都是容易解決的。例如斯坦納最小成本樹 (Steiner minimal tree) 以及最多葉生成樹 (maximum leaf spanning tree) 都是屬於 NP-complete的問題。在本研究中，我們計畫研究的是特殊圖形上的局部連通生成樹問題，局部連通生成樹 (locally connected spanning tree) 已經被證明為 NP-complete。本計畫主要是在 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 演算法。以上這兩個演算法均可測定圖是否含有局部連通生成樹。如果有，我們將產生此局部連通生成樹。 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 project, we study the problem of finding locally connected spanning trees which has been proven to be NP-complete on general graphs. We plan to design polynomial-time algorithms for some graph classes such as 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 plan to 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, we try to propose an O(n)-time algorithm for finding locally connected spanning trees on circular-arc graphs.

Keyword(s)

生成樹
圖類
誘導子圖
多項式時間
演算法
spanning tree
graph class
induced subgraph
polynomial-time
algorithm

DSpace CRIS

Locally Connected Spanning Trees on Graphs

Details

Description