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

• Adler, Jonathan D

Contributors

• Martin, William J.
• Dougherty, Daniel J.

Degree

• MS

Unit

• Mathematical Sciences

Publisher

• Worcester Polytechnic Institute

Language

• English

Identifier

• etd-042709-164059

Keyword

• clique width
• Graph Theory
• logic
• tree decompositions

Advisor

• Dougherty, Daniel J.
• Martin, William J.

Defense date

• 2008-04-30

Year

• 2009

Date created

• 2009-04-27

Resource type

• Report

Rights statement

• In Copyright

Last modified

• 2023-10-06