Parallel N-free order recognition

Abstract : Parallel algorithms for recognizing and representing N-free orders are proposed for different models of parallel random access machine (PRAM). The algorithms accept as input a transitively reduced directed graph with n vertices and m edges. They respectively run in time O(log n) using n + m processors in the EREW model and in constant time using n^2 processors in the CRCW PRAM model. Algorithms for distributed-memory machines are also proposed.
Complete list of metadatas

https://hal.inria.fr/inria-00471609
Contributor : Laurent Viennot <>
Submitted on : Thursday, April 8, 2010 - 4:13:33 PM
Last modification on : Monday, May 6, 2019 - 11:49:50 AM
Long-term archiving on : Friday, July 9, 2010 - 8:38:57 PM

Files

tcs97.pdf
Files produced by the author(s)

Identifiers

Citation

Laurent Viennot. Parallel N-free order recognition. Theoretical Computer Science, Elsevier, 1997, 175, pp.393-406. ⟨10.1016/S0304-3975(96)00210-1⟩. ⟨inria-00471609⟩

Share

Metrics

Record views

173

Files downloads

151