En graf är en mycket viktig struktur för att beskriva många tillämpningar i den verkliga världen. I många tillämpningar, såsom beroendediagram och skuldgrafer, är det ett viktigt problem att hitta och ta bort cykler för att göra dessa grafer vara cykelfria. Den gemensamma algoritmen leder ofta till ett utanförminnesundantag i varupersondatorn, och den kan inte utnyttja fördelen med flerkärniga datorer. Detta dokument introducerar ett nytt problem, cykeldetektering och avlägsnande med vertex prioritet. Den föreslår en multithreading iterativ algoritm för att lösa detta problem för storskaliga grafer på persondatorer. Algoritmen omfattar tre huvudsteg: förenkling för att minska skalan av grafen, beräkning av starkt anslutna komponenter, och cykeldetektering och borttagning enligt en fördefinierad prioritering parallellt. Denna algoritm undviker undantag ur minnet genom förenkling och iteration, och den utnyttjar fördelen av multicore datorer genom multi-threading parallellism. Fem olika versioner av den föreslagna algoritmen jämförs med experiment, och resultaten visar att den parallella iterativa algoritmen överträffar de andra, och förenkling kan effektivt förbättra algoritmens prestanda.
I REF införde författarna ett nytt problem: cykeldetektering och borttagning med vertex prioritet.
A Multi-Threading Algorithm to Detect and Remove Cycles in Vertex- and Arc-Weighted Digraph
{'venue': 'Algorithms', 'journal': 'Algorithms', 'mag_field_of_study': ['Mathematics', 'Computer Science']}