CMSO-transducing tree-like graph decompositions
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910202205306880 |
|---|---|
| author | Campbell, Rutger Guillon, Bruno Kanté, Mamadou Moustapha Kim, Eun Jung Köhler, Noleen |
| author_facet | Campbell, Rutger Guillon, Bruno Kanté, Mamadou Moustapha Kim, Eun Jung Köhler, Noleen |
| contents | We give $\operatorname{CMSO}$-transductions that, given a graph $G$, output its modular decomposition, its split decomposition and its bi-join decomposition. This improves results by Courcelle [Logical Methods in Computer Science, 2006] who gave such transductions using order-invariant $\operatorname{MSO}$, a strictly more expressive logic than $\operatorname{CMSO}$. Our methods more generally yield $\operatorname{C}_2 \operatorname{MSO}$-transductions that output the canonical decompositions of weakly-partitive set systems and weakly-bipartitive systems of bipartitions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04970 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | CMSO-transducing tree-like graph decompositions Campbell, Rutger Guillon, Bruno Kanté, Mamadou Moustapha Kim, Eun Jung Köhler, Noleen Logic in Computer Science Computational Complexity Discrete Mathematics Formal Languages and Automata Theory We give $\operatorname{CMSO}$-transductions that, given a graph $G$, output its modular decomposition, its split decomposition and its bi-join decomposition. This improves results by Courcelle [Logical Methods in Computer Science, 2006] who gave such transductions using order-invariant $\operatorname{MSO}$, a strictly more expressive logic than $\operatorname{CMSO}$. Our methods more generally yield $\operatorname{C}_2 \operatorname{MSO}$-transductions that output the canonical decompositions of weakly-partitive set systems and weakly-bipartitive systems of bipartitions. |
| title | CMSO-transducing tree-like graph decompositions |
| topic | Logic in Computer Science Computational Complexity Discrete Mathematics Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2412.04970 |