<p>While doing some research on topological sorting I came across a paper <a href="http://sciencelinks.jp/j-east/article/200409/000020040904A0317944.php" rel="nofollow">Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R.</a> which claims a recursive divide-and-conquer algorithm that </p>

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

<p>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.</p>

<p>I found few references in English papers (such as <a href="http://www.cs.brown.edu/~ws/papers/scc.pdf" rel="nofollow">this</a>), but none does more then mention in.</p>

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

CC BY-SA 3.0
2011-09-09T19:14:32.867Z
I don't think the paper is behind pay wall.  I put the [link](http://ci.nii.ac.jp/els/110002712158.pdf?id=ART0002995422&type=pdf&lang=jp&host=cinii&order_no=&ppv_type=0&lang_sw=&no=1315595039&cp=) so that others can get the paper.
Snowie
CC BY-SA 3.0
2011-09-10T22:01:58.570Z
Unfortunately, the provided link seems to have expired
chf
CC BY-SA 3.0
2011-09-11T14:48:40.533Z
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](http://www.ijicic.org/icic07-is03-13-1.pdf), which contains the email addresses of the authors.
Snowie
<reference-request><graph-algorithms><dc.parallel-comp><directed-acyclic-graph>
Recursive parallel topological sorting in linear time
chf
# Recursive parallel topological sorting in linear time

(Asked by: username_0 on 2011-09-09)

While doing some research on topological sorting I came across a paper [Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R.](http://sciencelinks.jp/j-east/article/200409/000020040904A0317944.php) 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](http://www.cs.brown.edu/~ws/papers/scc.pdf)), but none does more then mention in.

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

**Tags:** reference-request, graph-algorithms, dc.parallel-comp, directed-acyclic-graph
> **Comments:**
> **username_1**: I don't think the paper is behind pay wall.  I put the [link](http://ci.nii.ac.jp/els/110002712158.pdf?id=ART0002995422&type=pdf&lang=jp&host=cinii&order_no=&ppv_type=0&lang_sw=&no=1315595039&cp=) so that others can get the paper.  
> **username_0**: Unfortunately, the provided link seems to have expired  
> **username_1**: 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](http://www.ijicic.org/icic07-is03-13-1.pdf), which contains the email addresses of the authors.  

---

## 0 answers

