Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with spanning tree:
TR18-049 | 14th March 2018
Stasys Jukna, Hannes Seiwert

Greedy can also beat pure dynamic programming

Revisions: 1

Many dynamic programming algorithms are ``pure'' in that they only use min or max and addition operations in their recursion equations. The well known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^2\log n)$ operations. We prove that any pure DP algorithm ... more >>>

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