Dissertation
Dissertation > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory

Interval Graph and Tree-like Decomposition

Author ZhangChuanFang
Tutor WuYaoZuo
School Shanghai Jiaotong University
Course Applied Mathematics
Keywords Interval graph tree decomposition tree width eliminition width hypertree decomposition query decomposition
CLC O157.5
Type Master's thesis
Year 2010
Downloads 55
Quotes 0
Download Dissertation

Tree-like structure is an important structure arising from nature science and mathematics. It has wide applications in many fields, such as graph algorithm, computer science, biological mathematics and so on. Tree-like decomposition is an important tool in describing the tree-likeness of graphs, so it needs to be well studied.In this paper, we first introduce interval graphs which have simple tree-like structure, and then we discuss the basic properties and equivalent descriptions of interval graphs and proper interval graphs. Second, several tree-like decomposition methods are mainly presented:We deal with tree decomposition and tree width of graphs and hypergraphs, which play a central position in graph structure; Then we propose the notion of elimination width, and get the recursive equation of tree width and elimination width respectively, so that we draw the conclusion that they are equal. Furthermore, we closely study the elimination decomposition of hypergraphs. The corresponding relations between tree decomposition and elimi-nation decomposition are discussed, and we prove them under the new definition of elimination width as well. At last, we discuss some decomposition methods of hypergraphs, including query decomposition, hypertree decomposition and so on. Moreover, the relations between tree width, query width and hypertree width of hypergraphs are shown.

Related Dissertations
More Dissertations