Sorting can exponentially speed up pure dynamic programming

DOI10.1016/j.ipl.2020.105962zbMath1441.68305arXiv2012.12838OpenAlexW3015963488MaRDI QIDQ783692

Hannes Seiwert, Stasys P. Jukna

Publication date: 4 August 2020

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.12838

zbMATH Keywords

computational complexitydynamic programmingspanning treeMST problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Greedy can beat pure dynamic programming
• A note on practical construction of maximum bandwidth paths.
• On a routing problem
• A Dynamic Programming Approach to Sequencing Problems
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
• The steiner problem in graphs
• A Theorem on Boolean Matrices
• Subtraction-free complexity, cluster transformations, and spanning trees

This page was built for publication: Sorting can exponentially speed up pure dynamic programming