✦ LIBER ✦

A simplified correctness proof for a well-known algorithm computing strongly connected components

✍ Scribed by Ingo Wegener

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 44 KB
Volume: 83
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(01)00306-4

No coin nor oath required. For personal study only.

✦ Synopsis

The computation of the strongly connected components of a directed graph is one of the fundamental algorithmic graph problems. Linear-time algorithms with simple implementations are known. Here a simplified correctness proof for one of these algorithms is presented.

📜 SIMILAR VOLUMES

A new connected components algorithm for

A new connected components algorithm for virtual memory computers

✍ Ronald Lumia; Linda Shapiro; Oscar Zuniga 📂 Article 📅 1983 🏛 Elsevier Science ⚖ 855 KB

A Fast Algorithm for Image Component Lab

A Fast Algorithm for Image Component Labeling with Local Operators on Mesh Connected Computers

✍ H.C. Shi; G.X. Ritter 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 562 KB

A new parallel algorithm for image component labeling with local operators on SIMD mesh connected computers is presented. This algorithm provides a positive answer to the open question of whether there exists an \(O(n)\)-time and \(O(\log n)\)-space local labeling algorithm on SIMD mesh connected co