Abstract
In this paper, we demonstrate a deterministic algorithm that approximates
the optimal path cover on various graphs and networks derived from a wide range of realworld problems. Based on the 1
-Approximation Path Cover Algorithm by Moran et al., we
first organize the original algorithm into two versions - one with redundant edge removal
and one without. To compare the two versions of algorithms, we prove the number of
redundant edges for any general graphs to analyze the effects of edge removal. We also
analyze theoretical guarantees of the two algorithms. To test the time complexity and
performance, we conduct numerical tests on graphs with various structures and random
weights, from structured ring graphs to random graphs, such as Erd˝os-R´enyi graphs. The
tests demonstrate the advantage in memory saving of the algorithm that does not remove
any redundant edges and time saving of the other one, especially on large and high density
graphs. We also perform tests on various graphs and networks derived from a wide range of
real-world problems to suggest the effectiveness and applicability of both algorithms.
the optimal path cover on various graphs and networks derived from a wide range of realworld problems. Based on the 1
-Approximation Path Cover Algorithm by Moran et al., we
first organize the original algorithm into two versions - one with redundant edge removal
and one without. To compare the two versions of algorithms, we prove the number of
redundant edges for any general graphs to analyze the effects of edge removal. We also
analyze theoretical guarantees of the two algorithms. To test the time complexity and
performance, we conduct numerical tests on graphs with various structures and random
weights, from structured ring graphs to random graphs, such as Erd˝os-R´enyi graphs. The
tests demonstrate the advantage in memory saving of the algorithm that does not remove
any redundant edges and time saving of the other one, especially on large and high density
graphs. We also perform tests on various graphs and networks derived from a wide range of
real-world problems to suggest the effectiveness and applicability of both algorithms.
| Original language | English |
|---|---|
| Title of host publication | 2024 HAWAII UNIVERSITY INTERNATIONAL CONFERENCES |
| Subtitle of host publication | SCIENCE, TECHNOLOGY & ENGINEERING, ARTS, MATHEMATICS & EDUCATION |
| Place of Publication | PRINCE WAIKIKI RESORT, HONOLULU, HAWAII |
| Pages | 1-19 |
| State | Published - Jun 1 2024 |
Keywords
- Pure