Applications of Lexicographic Breadth-First Search to Modular Decomposition, Split Decomposition, and Circle Graphs | Posted on:2012-02-15 | Degree:Ph.D | Type:Thesis | University:University of Toronto (Canada) | Candidate:Tedder, Marc | Full Text:PDF | GTID:2458390011952351 | Subject:Computer Science | Abstract/Summary: | | This thesis presents the first sub-quadratic circle graph recognition algorithm, and develops improved algorithms for two important hierarchical decomposition schemes: modular decomposition and split decomposition. The modular decomposition algorithm results from unifying two different approaches previously employed to solve the problem: divide-and-conquer and factorizing permutations. It runs in linear-time, and is straightforward in its understanding, correctness, and implementation. It merely requires a collection of trees and simple traversals of these trees. The split-decomposition algorithm is similar in being straightforward in its understanding and correctness. An efficient implementation of the algorithm is described that uses the union-find data-structure. A novel charging argument is used to prove the running-time. The algorithm is the first to use the recent reformulation of split decomposition in terms of graph-labelled trees. This facilitates its extension to circle graph recognition. In particular, it allows us to efficiently apply a new lexicographic breadth-first search characterization of circle graphs developed in the thesis. Lexicographic breadth-first search is additionally responsible for the efficiency of the split decomposition algorithm, and contributes to the simplicity of the modular decomposition algorithm. | Keywords/Search Tags: | Decomposition, Lexicographic breadth-first search, Algorithm, Circle | | Related items |
| |
|