| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6424177 | European Journal of Combinatorics | 2014 | 8 Pages |
Abstract
We demonstrate that the greedy algorithm for reduction of divisors on metric graphs need not terminate by modeling the Euclidean algorithm in this context. We observe that any infinite reduction has a well defined limit, allowing us to treat the greedy reduction algorithm as a transfinite algorithm and to analyze its running time via ordinal numbers. Matching lower and upper bounds on worst case running time of O(Ïn) are provided.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Spencer Backman,