Treewidth, Pathwidth and Cospan Decompositions
Reference
Christoph Blume, H.J. Sander Bruggink, Martin Friedrich, and Barbara König. Treewidth, pathwidth and cospan decompositions. In Proceedings of GT-VMT 2011, Electronic Communications of the EASST, 2011.
Abstract
We will revisit the categorical notion of cospan decompositions of graphs and compare it to the well-known notions of path decomposition and tree decomposition from graph theory. More specifically, we will define several types of cospan decompositions with appropriate width measures and show that these width measures coincide with pathwidth and treewidth. Such graph decompositions of small width are used to efficiently decide graph properties, for instance via graph automata.
Suggested BibTeX entry:
@inproceedings{bbfk:decomp11,
author = {Christoph Blume and H.J. Sander Bruggink and Martin Friedrich and Barbara K{\"o}nig},
booktitle = {Proceedings of GT-VMT 2011},
series = {Electronic Communications of the EASST},
title = {Treewidth, Pathwidth and Cospan Decompositions},
year = {2011}
}
