Etd

 

Graph Decompositions and Monadic Second Order Logic Public

Downloadable Content

open in viewer

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.

Creator
Contributors
Degree
Unit
Publisher
Language
  • English
Identifier
  • etd-042709-164059
Keyword
Advisor
Defense date
Year
  • 2009
Date created
  • 2009-04-27
Resource type
Rights statement
License

Relationships

In Collection:

Items

Permanent link to this page: https://digital.wpi.edu/show/sb397840v