Treewidth, pathwidth and cospan decompositions with applications to ...

Reference

Christoph Blume, H.J. Sander Bruggink, Martin Friedrich, and Barbara König. Treewidth, pathwidth and cospan decompositions with applications to graph-accepting tree automata. Journal of Visual Languages and Computing, 24(3):192–206, 2013.

Abstract

We 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 measure coincide with pathwidth and treewidth. Such graph decompositions of small width are used to efficiently decide graph properties, for instance via graph automata. Hence, we will given an application by defining graph-accepting tree automata, thus integrating previous work by Courcelle into the setting of cospan decompositions. Furthermore, we will show that, regardless whether we consider path or tree decompositions, we arrive at the same notion of recognizability.

Suggested BibTeX entry:

@article{bbfk:decomp2013,
    author = {Christoph Blume and H.J. Sander Bruggink and Martin Friedrich and Barbara K{\"o}nig},
    journal = {Journal of Visual Languages and Computing},
    number = {3},
    pages = {192-206},
    title = {Treewidth, pathwidth and cospan decompositions with applications to graph-accepting tree automata},
    volume = {24},
    year = {2013}
}

This work is not available online here.