Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > MST PROBLEM:
Reports tagged with MST problem:
TR19-158 | 11th November 2019
Stasys Jukna, Hannes Seiwert

Sorting Can Exponentially Speed Up Pure Dynamic Programming

Many discrete minimization problems, including various versions of the shortest path problem, can be efficiently solved by dynamic programming (DP) algorithms that are ``pure'' in that they only perform basic operations, as $\min$, $\max$, $+$, but no conditional branchings via if-then-else in their recursion equations. It is known that any ... more >>>




ISSN 1433-8092 | Imprint