Width, depth, and space: tradeoffs between branching and dynamic programming

DOI10.3390/a11070098zbMath1461.68147MaRDI QIDQ2287480

Li-Hsuan Chen, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil

Publication date: 21 January 2020

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a11070098

zbMATH Keywords

dynamic programming; treewidth; branching algorithm; treedepth; space lower bound

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

68R10: Graph theory (including graph drawing) in computer science

90C39: Dynamic programming