Abstract-Vi anser att det grundläggande algoritmiska problemet med att hitta en cykel av minsta vikt i en viktad graf. I synnerhet visar vi att den minsta vikt cykel problem i en oriktad n-node graf med kant vikter i {1,..., M } eller i en riktad n-node graf med kant vikter i {-M,. .., M } och inga negativa cykler kan effektivt minskas till att hitta en minsta vikt triangel i en  till (n)-node oriktad graf med vikter i {1,..., O(M )}. Grovt sagt innebär våra minskningar följande överraskande fenomen: en minimicykel med ett godtyckligt antal viktade kanter kan "kodas" med endast tre
Det visades dock i REF att problemet med minimiviktcykeln i riktade grafer kan reduceras till problemet att hitta en minimitriangeln i en oriktad graf vilket innebär att minimiviktcykeln i riktade grafer kan beräknas i Õ(M n  på) tid, vilket förbättrar det ursprungliga resultatet.
Minimum Weight Cycles and Triangles: Equivalences and Algorithms
{'venue': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'journal': '2011 IEEE 52nd Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}