Dynamic Programming and Fast Matrix Multiplication

DOI10.1007/11841036_27MaRDI QIDQ5449535zbMATH OpenOpenAlexFDO

Authors Frederic Dorn

Publication date 11 March 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11841036_27

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• Faster algorithms on branch and clique decompositions
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• On two techniques of combining branching and treewidth
• STACS 2004
• Dynamic programming and planarity: improved tree-decomposition based algorithms

Cited in

(27)

• Computational study on planar dominating set problem
• Computational study on a PTAS for planar dominating set problem
• Subexponential fixed-parameter algorithms for partial vector domination
• Twin-width and polynomial kernels
• On the optimality of pseudo-polynomial algorithms for integer programming
• (Total) vector domination for graphs with bounded branchwidth
• Graph minors and parameterized algorithm design
• On the Boolean-width of a graph: structure and applications
• Subexponential fixed-parameter algorithms for partial vector domination
• New analysis and computational study for the planar connected dominating set problem
• A Linear Kernel for Planar Feedback Vertex Set
• How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
• Boolean-width of graphs
• A strengthened analysis of an algorithm for dominating set in planar graphs
• Subexponential parameterized algorithms
• Confronting intractability via parameters
• Coverability and sub-exponential parameterized algorithms in planar graphs
• On the optimality of pseudo-polynomial algorithms for integer programming
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• Tensor network complexity of multilinear maps
• scientific article; zbMATH DE number 6412845 (Why is no real title available?)
• Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
• Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• On the minimum corridor connection problem and other generalized geometric problems
• Dynamic programming and planarity: improved tree-decomposition based algorithms

This page was built for publication: Dynamic Programming and Fast Matrix Multiplication

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