Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
Bas van Geffen, Bart Jansen, Arnoud de Kroon, Rolf Morel • Journal of Graph Algorithms and Applications
(2020)
Many combinatorial problems can be solved in time $\mathcal{O}^*(c^{\mathrm{tw}})$ on graphs of treewidth $\mathrm{tw}$, for a problem-specific constant $c$. In several cases, matching upper and lower bounds on $c$ are known based on the St...
DOAJ
Open Access (DOAJ)
DOI:
10.7155/jgaa.00542