What is recorded here?
Arlazarov, Dinitz, M.A.Kronrod and Faradzhev tabulated unions over small blocks of intermediate vertices to compute Boolean relation products and acyclic graph closure in O(n^3/ln n) elementary operations. A directed network answers questions such as whether one place can reach another by following arrows. Computing every answer by checking every possible intermediate vertex takes cubic work in a familiar baseline. This1970 note groups intermediate vertices into small blocks. For each block it precomputes the possible unions of outgoing destinations, so a later row can select a stored result instead of rebuilding the same union. Choosing blocks of logarithmic size keeps those tables manageable and saves a logarithmic factor in the authors’ operation count. The note applies the composition lemma along the ranks of an acyclic graph. A graph with a directed cycle cannot be ranked this way directly: the paper relies on existing reductions through a graph whose vertices represent strongly connected components. The construction later became associated with the name method of Four Russians. That nickname is not a nationality attribution. The original identifies M.Kronrod as the source of its lemma, while all four authors remain responsible for the article. This is a historical algorithmic improvement under a declared representation and operation model, not a claim that it is always the fastest practical method today.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
The original direct result concerns acyclic graph closure with O(n^3/log n) elementary operations and table lookup; general graphs require the cited condensation/rank reductions. Lookup, storage and bit-operation assumptions remain part of the computational model. This account follows a transcription of the short original; it does not supply a certified formula transcription or independent proof reconstruction. Finite examples do not certify the complete asymptotic argument or a modern runtime benchmark. M. A. Kronrod is Mikhail Kronrod.
Read the original work
- Arlazarov, Dinitz, M.A.Kronrod and Faradzhev, economical transitive closure (1970) — original Russian web extraction
- Modern English transcription of the1970 two-page closure note — auxiliary reading aid
- Math-Net original bibliographic entry and full byline
- Math-Net linked author identities: Mikhail Aleksandrovich Kronrod
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Vladimir L'vovich Arlazarov; Yefim Dinitz; Mikhail Aleksandrovich Kronrod; Igor Aleksandrovich Faradzhev
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
Arlazarov, Dinitz, Kronrod and Faradzhev: faster graph reachability through subset tabulation
Arlazarov, Dinitz, M.A.Kronrod and Faradzhev tabulated unions over small blocks of intermediate vertices to compute Boolean relation products and acyclic graph closure in O(n^3/ln n) elementary operations.
A directed network answers questions such as whether one place can reach another by following arrows. Computing every answer by checking every possible intermediate vertex takes cubic work in a familiar baseline. This1970 note groups intermediate vertices into small blocks. For each block it precomputes the possible unions of outgoing destinations, so a later row can select a stored result instead of rebuilding the same union. Choosing blocks of logarithmic size keeps those tables manageable and saves a logarithmic factor in the authors’ operation count. The note applies the composition lemma along the ranks of an acyclic graph. A graph with a directed cycle cannot be ranked this way directly: the paper relies on existing reductions through a graph whose vertices represent strongly connected components. The construction later became associated with the name method of Four Russians. That nickname is not a nationality attribution. The original identifies M.Kronrod as the source of its lemma, while all four authors remain responsible for the article. This is a historical algorithmic improvement under a declared representation and operation model, not a claim that it is always the fastest practical method today.
Scientific scope
The original direct result concerns acyclic graph closure with O(n^3/log n) elementary operations and table lookup; general graphs require the cited condensation/rank reductions. Lookup, storage and bit-operation assumptions remain part of the computational model. This account follows a transcription of the short original; it does not supply a certified formula transcription or independent proof reconstruction. Finite examples do not certify the complete asymptotic argument or a modern runtime benchmark. M. A. Kronrod is Mikhail Kronrod.
People and systems
Vladimir L'vovich Arlazarov; Yefim Dinitz; Mikhail Aleksandrovich Kronrod; Igor Aleksandrovich Faradzhev
Original sources
- Arlazarov, Dinitz, M.A.Kronrod and Faradzhev, economical transitive closure (1970) — original Russian web extraction
- Modern English transcription of the1970 two-page closure note — auxiliary reading aid
- Math-Net original bibliographic entry and full byline
- Math-Net linked author identities: Mikhail Aleksandrovich Kronrod