کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421626 684923 2015 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Towards Compositional Graph Theory
ترجمه فارسی عنوان
به سوی نظریه گراف ترکیبی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Decomposing graphs into simpler graphs is one of the central concerns of graph theory. Investigations have revealed deep concepts such as modular decomposition, tree width or rank width, which measure—in different ways—the structural complexity of a graph's topology. Courcelle and others have shown that such concepts can be used to obtain efficient algorithms for families of graphs that are amenable to decomposition (e.g. those that have bounded tree-width). These algorithms, in turn, are of course of use in computer science, where graphs are ubiquitous. In this paper we take the first steps towards understanding notions of decomposition in graph theory compositionally, and more generally, in a categorical setting: category theory, after all, is the mathematics of compositionality.We introduce the concept of ∪–matrices (cup-matrices). Like ordinary matrices, ∪-matrices are the arrows of a PROP: we give a presentation, extending the work of Lafont, and Bonchi, Zanasi and the second author. A variant of ∪-matrices is then used in the development of a novel algebra of simple graphs, the lingua franca of graph theory. The algebra is that of a certain symmetric monoidal theory: ∪-matrices—akin to adjacency matrices—encode the graphs' topology.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 319, 21 December 2015, Pages 121-136