Computing Tree Decompositions

DOI10.1007/978-3-030-42071-0_14MaRDI QIDQ5042458zbMATH OpenOpenAlexFDO

Authors Michał Pilipczuk

Publication date 19 October 2022

Published in Treewidth, Kernels, and Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-42071-0_14

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Algorithms finding tree-decompositions of graphs
• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• Approximate tree decompositions of planar graphs in linear time
• An improved algorithm for finding tree decompositions of small width
• An improvement of Reed's treewidth approximation

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Approximating clique-width and branch-width
• Canonizing Graphs of Bounded Tree Width in Logspace
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Constructive algorithm for path-width of matroids
• Constructive linear time algorithms for branchwidth
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Cutwidth: obstructions and algorithmic aspects
• Definability equals recognizability for graphs of bounded treewidth
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• Finding branch-decompositions of matroids, hypergraphs, and more
• Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
• Graph expansion and the unique games conjecture
• Graph minors. XIII: The disjoint paths problem
• Graph minors. XX: Wagner's conjecture
• 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 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2080246 (Why is no real title available?)
• scientific article; zbMATH DE number 6862107 (Why is no real title available?)
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Inapproximability of treewidth and related problems
• Parameterized algorithms
• Query evaluation via tree-decompositions
• The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
• Upper bounds on the size of obstructions and intertwines

Cited in

(8)

• Null decomposition of trees
• Incremental and Efficient Computation of Families of Component Trees
• Tree Decomposition with Function Filtering
• An Iterative Heuristic Algorithm for Tree Decomposition
• scientific article; zbMATH DE number 1844471 (Why is no real title available?)
• Optimizing tree decompositions in MSO
• Tree decomposition
• Computing tree decompositions with small independence number

This page was built for publication: Computing Tree Decompositions

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