2020/04/10 by Stasys Jukna, Hannes Seiwert
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Arithmetic #Combinatorics #Computer science #Dynamic programming #Graph #Mathematical optimization #Mathematics #Minification #Path (computing) #Recursion (computer science) #Shortest path problem #Sorting #Vertex (graph theory) #cs.CC #sort
paper · pdf · doi:10.1016/j.ipl.2020.105962
published as Information Processing Letters 159-160 (2020), article Nr. 105962
openalex publication_date 2020/04/10 · arxiv created 2020/12/23 · arxiv updated 2020/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 pure (min,+) DP algorithm solving the minimum weight spanning tree problem on undirected n-vertex graphs must perform at least 2Ω(√(n)) operations. We show that this problem can be solved by a pure (min,max,+) DP algorithm performing only O(n3) operations. The algorithm is essentially a (min,max) algorithm: addition operations are only used to output the final values. The presence of both min and max operations means that now DP algorithms can sort: this explains the title of the paper.