Document Type masters report Author Name Adler, Jonathan D URN etd-042709-164059 Title Graph Decompositions and Monadic Second Order Logic Degree MS Department Mathematical Sciences Advisors William Martin, Advisor Daniel Dougherty, Advisor Keywords clique width tree decompositions logic graph theory Date of Presentation/Defense 2008-04-30 Availability unrestricted
A tree decomposition is a tool which allows for analysis of the underlying tree structure of graphs which are not trees. Given a class of graphs with bounded tree width, many NP-complete problems can be computed in linear time for graphs in the class. Clique width of a graph G is a measure of the number of labels required to construct G using several particular graph operations. For any integer k, both the class of graphs with tree width at most k and the class of graphs with clique width at most k have a decidable monadic second order theory. In this paper we explore some recent results in applying these graph measures and their relation to monadic second order logic.
Browse by Author | Browse by Department | Search all available ETDs
Questions? Email email@example.com