For a given ordered graph (G,<), we consider the smallest (strongly) chordal graph G' containing G with < as a (strongly) perfect elimination ordering. We call (G,<) a compact representation of G'. We show that the computation of a depth-first search tree and a breadth-first search tree can be done in polylogarithmic time with a linear processor number with respect to the size of the compact representation in parallel. We consider also the problems to find a maximum clique and to develop a data structure extension that allows an adjacency query in polylogarithmic time.
展开▼
