Rapport de Recherche Litp /
Litp research reports
16 pages - Février/February 1995 - Document en anglais.
PostScript : Ko /Kb
Titre / Title: Parallel N-free Order Recognition
Abstract : Parallel algorithms for recognizing and representing N-free orders are proposed for different models of parallel random access machines (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 PRAM model and in constant time using n2 processors in the CRCW PRAM model. Algorithms for distributed-memory machines are also proposed.
Publications internes Litp 1995 / Litp research reports 1995