Structured Decompositions: Structural and Algorithmic Compositionality
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915293963485184 |
|---|---|
| author | Bumpus, Benjamin Merlin Kocsis, Zoltan A. Master, Jade Edenstar Minichiello, Emilio |
| author_facet | Bumpus, Benjamin Merlin Kocsis, Zoltan A. Master, Jade Edenstar Minichiello, Emilio |
| contents | We introduce structured decompositions, category-theoretic structures which simultaneously generalize notions from graph theory (including treewidth, layered treewidth, co-treewidth, graph decomposition width, tree independence number, hypergraph treewidth and H-treewidth), geometric group theory (specifically Bass-Serre theory), and dynamical systems (e.g. hybrid dynamical systems). We define width functors, which provide a compositional way to analyze and relate different structural complexity measures, and establish a general duality between decompositions and completions of objects. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_06091 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Structured Decompositions: Structural and Algorithmic Compositionality Bumpus, Benjamin Merlin Kocsis, Zoltan A. Master, Jade Edenstar Minichiello, Emilio Category Theory Data Structures and Algorithms Combinatorics 18B10, 05C75 (Primary) 68W40 (Secondary) F.2.m; G.0 We introduce structured decompositions, category-theoretic structures which simultaneously generalize notions from graph theory (including treewidth, layered treewidth, co-treewidth, graph decomposition width, tree independence number, hypergraph treewidth and H-treewidth), geometric group theory (specifically Bass-Serre theory), and dynamical systems (e.g. hybrid dynamical systems). We define width functors, which provide a compositional way to analyze and relate different structural complexity measures, and establish a general duality between decompositions and completions of objects. |
| title | Structured Decompositions: Structural and Algorithmic Compositionality |
| topic | Category Theory Data Structures and Algorithms Combinatorics 18B10, 05C75 (Primary) 68W40 (Secondary) F.2.m; G.0 |
| url | https://arxiv.org/abs/2207.06091 |