Title page for ETD etd-042709-164059

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
Abstract 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.
Files	Jonathan_Adler_Project.pdf

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