2023/05/09 by Arjun Bhalla, Bhalla, Arjun
Engineering · #Advanced Optical Network Technologies #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Packing Problems #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2305.05121
openalex publication_date 2023/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Minimum Spanning Trees are a well-studied subset of graph problems. While classical algorithms have existed to solve these problems for decades, new variations and application areas are constantly being discovered. When dealing with large graph problems, however, memory constraints can often be limiting, especially when using these classical methods in memory restricted environments. In this work, we propose an augmentation of Prim's algorithm that can be empirically shown to solve MST problems with a reduction in auxiliary memory usage of over 90%, and a margin of error of less than 0.3%.