Etd
Graph Decompositions and Monadic Second Order Logic
ÖffentlichA 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
- Mitwirkende
- Degree
- Unit
- Publisher
- Language
- English
- Identifier
- etd-042709-164059
- Stichwort
- Advisor
- Defense date
- Year
- 2009
- Date created
- 2009-04-27
- Resource type
- Rights statement
- Zuletzt geändert
- 2023-10-06
Beziehungen
- In Collection:
Objekte
Artikel
Miniaturansicht | Titel | Sichtbarkeit | Embargo Release Date | Aktionen |
---|---|---|---|---|
|
Jonathan_Adler_Project.pdf | Öffentlich | Herunterladen |
Permanent link to this page: https://digital.wpi.edu/show/sb397840v