圖論支配相關問題與其應用

近三十年來，隨著計算機科學、電機與計算機工程及作業研究等領域的成長，圖形理論也呈現出爆炸性的發展，而其中支配相關問題可能是圖形理論中發展最為快速的。特別的是，從演算法角度去觀察支配相關問題的文獻在這其中佔了相當重要的比例。支配問題的概念其實也就是許多在作業研究的地域問題的模型。而根據許多在應用方面不同的需要，漸漸衍生出許多對應的支配相關問題樣式。在這篇博士論文中，我們將以電力支配問題、森林生成k 樹以及網路比對問題來做具體的討論。我們可以根據監管的規則將電力網路系統的監測問題化成圖論上的電力支配問題。由於一個電力支配集合具有傳遞監測的能力，使得目前這個問題只有在樹狀相關圖形上有多項式時間的演算法。所以我們希望能夠在別的特殊圖形上設計出有效率的演算法或是探討它的問題複雜度。在這篇論文中，我們在間隔圖及環狀圖上提出了線性時間的演算法，並證明電力支配在分裂圖上是NP 完備的。在沒有加權的圖形中，森林生成k 樹跟k 距離支配問題是完全等價的。在過去的幾年中被廣泛探討的森林生成星狀圖其實就是森林生成1 樹(k=1)。森林生成星狀圖問題是來自於比較基因學中的一個很重要的問題：多重序列基因比對。我們在這篇論文中分別針對森林生成k 樹在無向和有向的加權圖上都提出(k/k+1)的近似演算法。最後我們更進一步把圖論中支配問題的觀念推廣到生物資訊中常用到的星狀比對方法。我們將這個觀念應用到系統生物學中多重蛋白質交互作用網路比對的問題。多重蛋白質交互作用網路比對問題的動機是因為我們想要能夠在這些以細胞為單位的大型系統中，找出各種生物之間蛋白質基因演化的過程。我們提出的星狀比對方法配合上光譜圖論群集演算法，使得我們在五個真核生物的多重蛋白質交互作用網路比對中，不論在結果一致性和覆蓋性都凌駕於目前現在所有的演算法。

關鍵字

演算法；支配問題；網路比對；電力；森林生成星狀圖

並列摘要

Within the last thirty years, concurrent with the growth of such areas as computer science, electrical and computer engineering, and operations research, graph theory has seen explosive growth and perhaps the fastest-growing area within graph theory is the study of domination and related problems. In particular, there has appeared a significant portion of literature from an algorithmic point of view. The concept of domination in graph theory is a natural model for many location problems in operations research. According to different requirements for practical applications, there are various types of domination problem. In this dissertation we specifically consider power domination, spanning k-tree forest, and network alignment problem. The power system observation problem can be transformed into the graph-theoretic power domination problem according to the observation rules. Since a power dominating set has the capability of observing remote elements via propagation, there are only polynomial time algorithms for power domination problem on tree-type graphs. We would like to design efficient polynomial algorithms and investigate the problem complexity for power domination problems on other special graph classes. We show that the problem of finding the power domination number for split graphs is NP-complete. In addition, we present a linear time algorithm for an interval graph, if the interval ordering of the graph is provided, and show that the same result holds for the class of circular-arc graphs. For unweighted graphs, the spanning k-tree forest problem is equivalent to the k-distance domination problem. The spanning 1-tree forest problem has been known as the spanning star forest problem and investigated extensively in the past several years. This problem arises from aligning multiple genomic sequences, a basic bioinformatics task in comparative genomics. We show that this generalization of the spanning star forest, the spanning k-tree forest problem, can be (k/k+1)-approximated in polynomial time for both undirected and directed weighted graphs. Furthermore we extend the domination in graph theory to the star aligned method in bioinformatics, which is applied to multiple protein-protein interaction network alignment problem in system biology field. The search for such a network alignment is motivated by the intuition that evolution of genes happens within the context of the larger cellular system. We present our star aligned algorithm based on spectral clustering, which outperforms existing algorithms for global network alignment in coverage and consistency of the five available eukaryotic networks.

並列關鍵字

algorithm ； domination ； network alignment ； power ； star forest

參考文獻

[1] A. Aazami and M.D. Stilp. Approximation algorithms and hardness for domination

with propagation. In Proceedings of the 10th International Workshop on Approximation

Algorithms for Combinatorial Optimization Problems, APPROX’07, (2007) pp. 1–15.

[2] R. Anderson, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors.

In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science,

國際替代計量

圖論支配相關問題與其應用

主題瀏覽