Optimizing tree decompositions in MSO

MaRDI QIDQ5028484zbMATH OpenFDO

Authors Mikołaj Bojańczyk, Michał Pilipczuk

Publication date 9 February 2022

Full work available at URL https://arxiv.org/abs/1701.06937, https://lmcs.episciences.org/9029

zbMATH Keywords

treewidthtree decompositiontransductionMSO

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• scientific article; zbMATH DE number 6862107
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• \(k\)-best solutions of MSO problems on tree-decomposable graphs
• Computing Tree Decompositions
• Practical algorithms for MSO model-checking on tree-decomposable graphs

Cites work

• scientific article; zbMATH DE number 176761 (Why is no real title available?)
• scientific article; zbMATH DE number 176762 (Why is no real title available?)
• scientific article; zbMATH DE number 6862107 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Menger-like property of tree-cut width
• Algorithmic graph theory and perfect graphs
• Computing tree-depth faster than \(2^n\)
• Constructive algorithm for path-width of matroids
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Definability equals recognizability for graphs of bounded treewidth
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Enumeration of monadic second-order queries on trees
• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• Exploring the subexponential complexity of completion problems
• Finding branch-decompositions of matroids, hypergraphs, and more
• Graph structure and monadic second-order logic. A language-theoretic approach
• MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
• Query evaluation via tree-decompositions
• The vertex separation number of a graph equals its path-width
• Upper bounds on the size of obstructions and intertwines

Cited in

(4)

• Edge-treewidth: algorithmic and combinatorial properties
• Evaluation of an MSO-Solver
• scientific article; zbMATH DE number 6678444 (Why is no real title available?)
• scientific article; zbMATH DE number 6862107 (Why is no real title available?)

This page was built for publication: Optimizing tree decompositions in MSO

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028484)