Graph-Theoretic Domination and Related Problems with Applications
Date Issued
2009
Date
2009
Author(s)
Liao, Chung-Shou
Abstract
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.he 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,here are only polynomial time algorithms for power domination problem on tree-type graphs. We would like to design efficient polynomial algorithms and investigate theroblem 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. or 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.urthermore 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 thearger cellular system. We present our star aligned algorithm based on spectral clustering, which outperforms existing algorithms for global network alignment inoverage and consistency of the five available eukaryotic networks.
Subjects
algorithm
domination
network alignment
power
star forest
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-D93922018-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):574b49489eee71b49de61d0867abb975