Worcester Polytechnic Institute Electronic Theses and Dissertations Collection

Title page for ETD etd-042709-164059


Document Typemasters report
Author NameAdler, Jonathan D
URNetd-042709-164059
TitleGraph Decompositions and Monadic Second Order Logic
DegreeMS
DepartmentMathematical Sciences
Advisors
  • William Martin, Advisor
  • Daniel Dougherty, Advisor
  • Keywords
  • clique width
  • tree decompositions
  • logic
  • graph theory
  • Date of Presentation/Defense2008-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

    [WPI] [Library] [Home] [Top]

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