Composing dynamic programming tree-decomposition-based algorithms
From MaRDI portal
Publication:6606983
DOI10.46298/DMTCS.11069zbMATH Open1547.05235MaRDI QIDQ6606983FDOQ6606983
Authors: Julien Baste 
Publication date: 17 September 2024
Published in: Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)
Recommendations
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- The Fine Details of Fast Dynamic Programming over Tree Decompositions
- scientific article; zbMATH DE number 4060712
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Practical algorithms on partial k-trees with an application to domination-like problems
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
- 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)
