Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903641 | European Journal of Combinatorics | 2018 | 21 Pages |
Abstract
If edge costs are integers in range [0,C] then for both 1- and 2-matchings some faster scaling algorithms are known that find optimal solutions within O(Vα(E,V)logVElog(VC)) and O(VElog(VC)) time, respectively, where α denotes the inverse Ackermann function. So far, no efficient cost-scaling algorithm is known for finding a minimum-cost perfect triangle-free2-matching. The present paper fills this gap by presenting such an algorithm with time complexity of O(VElogVlog(VC)).
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
S. Artamonov, M. Babenko,