Department of Mathematics, Statistics, and Data Sciences1
Loyola Marymount University
Los Angeles, California

Institute of Mathematical Sciences²
Claremont Graduate University
Claremont, California

Implementation of 1/2-Approximation Path Cover Algorithm and Its Empirical Analysis

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.

View Paper