Document Typemasters report Author NameAdler, Jonathan D URNetd-042709-164059 TitleGraph Decompositions and Monadic Second Order Logic DegreeMS DepartmentMathematical Sciences AdvisorsWilliam Martin, Advisor Daniel Dougherty, Advisor Keywordsclique width tree decompositions logic graph theory Date of Presentation/Defense2008-04-30 Availabilityunrestricted

AbstractA 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.

FilesJonathan_Adler_Project.pdf

Browse by Author | Browse by Department | Search all available ETDs

Questions? Email etd-questions@wpi.eduMaintained by webmaster@wpi.edu