Optimal parallel algorithms for finding cut vertices and bridges of interval graphs. (English) Zbl 0764.68054

Summary: We present \(O(\log n)\) time algorithms in the EREW PRAM model, using \(n/\log n\) processors, to find cut vertices, bridges, and blocks (often called biconnected components) of an interval graph having \(n\) vertices. It is assumed the interval graph is represented by an interval model, with ends presorted. If the ends are not presorted, our algorithms, preceded by an optimal sort, from an \(O(\log n)\) time algorithm using \(n\) processors, which is shown to be optimal. The algorithms rely heavily on the parallel prefix algorithm.


68W15 Distributed algorithms
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI


[1] Akl, S.G., The design and analysis of parallel algorithms, (1989), Prentice-Hall Englewood Cliffs, NJ · Zbl 0704.68049
[2] Ben-Or, M., Lower bounds for algebraic computation trees, Proc. 15th ACM ann. symp. on theory of computing, 80-86, (1983)
[3] Bertossi, A.A.; Bonuccelli, M.A., Some parallel algorithms on interval graphs, Discrete appl. math., 16, 101-111, (1987) · Zbl 0636.68087
[4] Bollobos, B., Graph theory, (1979), Springer New York
[5] Cole, R., Parallel merge sort, SIAM J. comput., 17, 770-785, (1988) · Zbl 0651.68077
[6] Dekel, E.; Sahni, S., Binary trees and parallel scheduling algorithms, IEEE trans. comput., 32, 307-315, (1983) · Zbl 0513.68031
[7] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[8] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[9] Kim, S.K., Optimal parallel algorithms on sorted intervals, Proc. 27th ann. allerton conf. on comm., control, and computing, 766-775, (1989)
[10] Kruskal, C.P.; Rudolph, L.; Snir, M., The power of parallel prefix, IEEE trans. comput., 34, 965-968, (1985)
[11] Olariu, S.; Schwing, J.L.; Zhang, J., Optimal parallel algorithms for problems modelled by a family of intervals, Proc. 28th ann. allerton conf. on comm., control, and computing, 282-291, (1990)
[12] Preparata, F.P.; Shamos, M.I., Computational geometry: an introduction, (1988), Springer New York
[13] Ramkumar, G.D.S.; Pandu Rangan, C., Parallel algorithms on interval graphs, Proc. 1990 internat. conf. on parallel processing, Vol. 3, 72-74, (1990)
[14] Tarjan, R.E.; Vishkin, U., An efficient parallel biconnectivity algorithm, SIAM J. comput., 14, 862-874, (1985) · Zbl 0575.68066
[15] Tsin, Y.H.; Chin, F.Y., Efficient parallel algorithms for a class of graph theoretic problems, SIAM J. comput., 13, 580-599, (1984) · Zbl 0545.68060
[16] Yoshimura, T.; Kuh, E.S., Efficient algorithms for channel routing, IEEE trans. comput. aided design, 1, 25-35, (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.