University/Organization
Department of Mathematics, Statistics, and Data Sciences1
Loyola Marymount University
Los Angeles, California
Department of Mathematics, Statistics, and Data Sciences1
Loyola Marymount University
Los Angeles, California
Institute of Mathematical Sciences²
Claremont Graduate University
Claremont, California
Title
Implementation of 1/2-Approximation Path Cover Algorithm and Its Empirical Analysis
Synopsis
In this study, we refine a deterministic algorithm for approximating optimal path covers in graphs, based on Moran et al’s approach into two versions: with and without redundant edge removal. Testing on various graph types, including Erdős-Rényi, showed the first version saves 80% in memory, while the second cuts computation time by 60%, proving their applicability for real-world dense and complex graphs.