← 研踪 PaperTrailarXiv:2412.04970 · v7
CMSO-transductions for tree-like graph decompositions
首次提交 2024-12-06 19:41
版本更新 2026-11-02 21:35
雷达观测 2026-11-04 23:41
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v7 · 2026-11-02 21:35 · 最新观测版本
CMSO-transductions for tree-like graph decompositions
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.
查看此版本解读 →查看此版本原文 ↗