While doing some research on topological sorting I came across a paper Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R. which claims a recursive divide-and-conquer algorithm that

requires $O(n+m)$ processors and $O(\log^2m)$ time on a CREW-PRAM model

Unfortunately the paper is not only behind pay wall but is also in Japanese except for the abstract. I was able to obtain a copy, however only from the abstract and some contained (English) pseudocode I did not fully understand the details of the algorithm/analysis.

I found few references in English papers (such as this), but none does more then mention in.

Does anybody know of an English (or perhaps German?) description of the details of this algorithm?

  • $\begingroup$ I don't think the paper is behind pay wall. I put the link so that others can get the paper. $\endgroup$ – Snowie Sep 9 '11 at 19:14
  • $\begingroup$ Unfortunately, the provided link seems to have expired $\endgroup$ – chf Sep 10 '11 at 22:01
  • 1
    $\begingroup$ Sorry, I cannot figure out how to fix the link problem. Instead, you may want to contact the authors of the paper. The first and second authors of the paper wrote another paper, which contains the email addresses of the authors. $\endgroup$ – Snowie Sep 11 '11 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.