A provably fastest parallel algorithm for the recognition of the consecutive ones property with selected applications

Presented here is a parallel algorithm that decides if an m×n (0, 1)-matrix has the consecutive 1´s property for rows, and if so, turns the matrix into one with consecutive 1´s in each row by column permutation. The algorithm runs in optimal O(log(mn)) time with O(M(m)n log m/m+M(n)m² log n/n²) work on CREW PRAM where M(n) denotes the processor bound for multiplying two n×n matrices in O(log n) time and is o(n^2.376). We then show that this procedure can recognize doubly convex bipartite graphs in O(log n) time with O(M(n)) processors