×

zbMATH — the first resource for mathematics

Counting clique trees and computing perfect elimination schemes in parallel. (English) Zbl 0685.68050
Summary: In a previous result, the authors showed that a clique tree of a chordal graph can be constructed in O(log n) parallel computing time with \(O(n^ 3)\) processors on CRCW PRAM, where n is the number of nodes of the graph. It will be shown that this result can be extended in two ways. First, we show that from the parallel clique tree constructing algorithm we can derive an exact formula of counting clique trees of a labeled connected chordal graph. Next, we show that a perfect elimination scheme of a chordal graph can be computed in O(log n) time with \(O(n^ 2)\) processors on CREW PRAM once a clique tree of the graph is given. This implies that a perfect elimination scheme of a chordal graph can be computed on O(log n) time with \(O(n^ 3)\) processors on CRCW PRAM.

MSC:
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Azar, Y.; Vishkin, U., Tight comparison bounds on the complexity of parallel sorting, SIAM J. comput., 16, 458-464, (1987) · Zbl 0654.68070
[2] Balas, E.; Yu, C.S., Finding a maximum clique in an arbitrary graph, SIAM J. comput., 15, 1054-1068, (1986) · Zbl 0604.05024
[3] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. assoc. comput. Mach., 30, 479-513, (1983) · Zbl 0624.68087
[4] Buneman, P., A characterization on rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128
[5] Chang, G.J.; Nemhauser, G.L., Covering, packing and generalized perfection, SIAM. J. alg. disc. meth., 6, 109-132, (1985) · Zbl 0556.05055
[6] Cole, R.; Vishkin, U., Deterministic coin tossing with applications to optimal parallel List ranking, Inform. and control, 70, 32-53, (1986) · Zbl 0612.68044
[7] Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[8] Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-856, (1965) · Zbl 0132.21001
[9] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory B, 16, 47-56, (1974) · Zbl 0266.05101
[10] Gilbert, J.R.; Rose, D.J.; Edenbrandt, A., A separator theorem for chordal graphs, SIAM J. alg. disc. meth., 15, 306-313, (1984) · Zbl 0551.05049
[11] Golumbic, M.C., Algorithm graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0461.05037
[12] C.W. Ho, Fast Parallel Algorithms Related to Chordal Graphs, Ph.D. Dissertation, National Tsing University, Hsinchu, Taiwan, Rep. China.
[13] Ho, C.W.; Lee, R.C.T., Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, Inform. process. lett., 28, 301-309, (1988) · Zbl 0658.68079
[14] Kolen, A., The round-trip p-center and covering problem on a tree, Transportation sci., 19, 222-234, (1985) · Zbl 0606.90041
[15] Leighton, T., Tight bounds on the complexity of parallel sorting, IEEE trans. comput., 34, 344-354, (1985) · Zbl 0556.68024
[16] Lekkerkerker, C.G.; Boland, J.Ch., Representation of a finite graph by a set of intervals on the real line, Fund. math., 51, 45-64, (1962) · Zbl 0105.17501
[17] Monma, C.L.; Wei, V.K., Intersection graphs of paths in a tree, J. combin. theory B, 41, 141-181, (1986) · Zbl 0595.05062
[18] Moon, J.W., Various proofs of Cayley’s formula for counting trees, (), 70-78
[19] Naor, J.; Naor, M.; Schäffer, A.A., Fast parallel algorithms for chordal graphs, (), 355-364 · Zbl 0672.05055
[20] Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602
[21] Rose, D.J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (), 183-217
[22] Shiloach, Y.; Vishkin, U., An O(log n) parallel connectivity algorithm, J. algorithms, 3, 57-67, (1982) · Zbl 0494.68070
[23] Tarjan, R.E.; Vishkin, U., Finding biconnected components and computing tree functions in logarithmic parallel time, (), 12-20
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.