Jump to content

Rocha–Thatte cycle detection algorithm

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Rcorcs (talk | contribs) at 20:52, 16 June 2015 (←Created page with ''''Rocha-Thatte Algorithm'''<ref>{{citation|title=Distributed cycle detection in large-scale sparse graphs|first1=Rodrigo Caetano|last1=Rocha|first2=Bhalchandra|...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

Rocha-Thatte Algorithm[1] is a distributed algorithm in graph theory for detecting cycles on large-scale directed graphs based on the bulk synchronous message passing abstraction. This algorithm for detecting cycles by message passing is suitable to be implemented in distributed graph processing systems, and it is also suitable for implementations in systems for disk-based computations, such as the GraphChi[2], where the computation is mainly based on secondary memory. Disk-based computations are necessary when we have a single computer for processing large-scale graphs, and the computation exceeds the primary memory capacity.

References

  1. ^ Rocha, Rodrigo Caetano; Thatte, Bhalchandra (2015), Distributed cycle detection in large-scale sparse graphs
  2. ^ GraphChi: Large-scale graph computation on just a PC (PDF)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Rocha–Thatte_cycle_detection_algorithm&oldid=667252274"