Composing dynamic programming tree-decomposition-based algorithms

DOI10.46298/DMTCS.11069zbMATH Open1547.05235MaRDI QIDQ6606983FDOQ6606983

Julien Baste

Publication date: 17 September 2024

Published in: Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

zbMATH Keywords

graph partitiondynamic programmingtreewidthparameterized complexitydynamic programming core model

Mathematics Subject Classification ID

Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graph clustering
• Reducibility among Combinatorial Problems
• Balanced graph partitioning
• Which problems have strongly exponential complexity?
• Vertex and tree arboricities of graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Parameterized Algorithms
• Treewidth. Computations and approximations
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Compatibility of unrooted phylogenetic trees is FPT
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Partition the vertices of a graph into induced matchings
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Efficient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees
• On the vertex arboricity of planar graphs of diameter two
• The agreement problem for unrooted phylogenetic trees is FPT
• Diversity of solutions: an exploration through the lens of fixed-parameter tractability theory
• Treewidth of display graphs: bounds, brambles and applications
• Partition a graph with small diameter into two induced matchings

This page was built for publication: Composing dynamic programming tree-decomposition-based algorithms

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