An optimal parallel algorithm for node ranking of cographs Original Research Article

A ranking of a graph G is a mapping, ρ, from the vertices of G to the natural numbers such that for every path between any two vertices u and v, u≠v, with ρ(u) = ρ(v), there exists at least one vertex w on that path with ρ(w) > ρ(u) = ρ(v). The value ρ(v) of a vertex v is the rank of vertex v. A ranking is optimal if the largest rank assigned is the smallest among all rankings. The optimal ranking problem on a graph G is the problem of finding an optimal ranking on G. We persent a parallel algorithm which needs O(log n) time and n/log n processors on the EREW PRAM model for this problem on cographs.