Fast parallel algorithms for chordal graphs.

*(English)*Zbl 0672.05055This paper presents fast parallel algorithms concerning problems on chordal graphs, where efficient sequential algorithms are known.

One of the problems is the recognition of chordal graphs. The time bound is polylogarithmic and the processor bound is polynomial but not linear. The best known sequential algorithm needs only linear time. But the processor bound of this parallel algorithm is better than that of an earlier parallel algorithm of A. Edenbrandt. Here also fast parallel algorithms are presented, which construct a corresponding collection of subtrees of a tree, an elimination ordering, and minimum colouring, and a maximum weight independent set for any chordal graph.

P. Klein presented later a polylog time parallel algorithm for the construction of an elimination ordering for each chordal graph, which needs only a linear number of processors, and therefore also a recognition algorithm for chordal graphs with a linear processor bound. Only the time bound is a little bit worse than that of the algorithm of J. Naor, M. Naor, and A. Schäffer.

One of the problems is the recognition of chordal graphs. The time bound is polylogarithmic and the processor bound is polynomial but not linear. The best known sequential algorithm needs only linear time. But the processor bound of this parallel algorithm is better than that of an earlier parallel algorithm of A. Edenbrandt. Here also fast parallel algorithms are presented, which construct a corresponding collection of subtrees of a tree, an elimination ordering, and minimum colouring, and a maximum weight independent set for any chordal graph.

P. Klein presented later a polylog time parallel algorithm for the construction of an elimination ordering for each chordal graph, which needs only a linear number of processors, and therefore also a recognition algorithm for chordal graphs with a linear processor bound. Only the time bound is a little bit worse than that of the algorithm of J. Naor, M. Naor, and A. Schäffer.

Reviewer: E.Dahlhaus