Some parallel algorithms on interval graphs. (English) Zbl 0636.68087

Parallel algorithms are given for finding a maximum weighted clique, a maximum weighted independent set, a minimum clique cover, and a minimum weighted dominating set of an interval graph. Parallel algorithms are also given for finding a Hamiltonian circuit and the minimum bandwindth of a proper interval graph. The shared memory model (SMM) of parallel computers is used to obtain fast algorithms.


68R10 Graph theory (including graph drawing) in computer science
05C35 Extremal problems in graph theory
Full Text: DOI


[1] Awerbach, B; Israeli, A; Shiloach, Y, Finding Euler circuits in logarithmic parallel time, (), 249-257
[2] Bertossi, A.A, Finding Hamiltonian circuits in proper interval graphs, (), 97-101 · Zbl 0512.68046
[3] Booth, K; Johnson, J.H, Dominating sets in chordal graphs, SIAM J. comput., 11, 191-199, (1982) · Zbl 0485.05055
[4] Dekel, E; Nassimi, D; Sahni, S, Parallel matrix and graph algorithms, SIAM J. comput., 10, 657-675, (1981) · Zbl 0468.68044
[5] Dekel, E; Sahni, S, Parallel scheduling algorithms, Oper. res., 31, 24-49, (1983) · Zbl 0495.90045
[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] Gupta, U.I; Lee, D.T; Leung, J.Y.-T, Efficient algorithms for interval graphs and circular arc graphs, Networks, 12, 459-467, (1982) · Zbl 0493.68066
[9] Karp, R; Widgerson, A, A fast parallel algorithm for the maximal independent set problem, (), 266-272
[10] Kindervater, G.A.P; Lenstra, J.K, An introduction to parallelism in combinatorial optimization, Discrete appl. math., 14, 135-156, (1986) · Zbl 0593.90047
[11] Manacher, G.K; Smith, C.J, Efficient algorithms for new problems on interval graphs and interval models, (1984), manuscript
[12] Muller, D.E; Preparata, F.P, Bounds to complexities of networks for sorting and switching, J. ACM, 22, 195-201, (1975) · Zbl 0334.94007
[13] Orlin, J.B; Bonuccelli, M.A; Bovet, D.P, An O(n2) algorithm for coloring proper circular arc graphs, SIAM J. algebraic discrete methods, 2, 88-93, (1981) · Zbl 0496.68047
[14] Papadimitriou, C.H, The NP-completeness of the bandwidth minimization problem, Computing, 16, 263-270, (1976) · Zbl 0321.65019
[15] Quinn, M.J; Deo, N, Parallel graph algorithms, Comput. surveys, 16, 319-348, (1984) · Zbl 0567.68040
[16] Roberts, F.S, Discrete mathematical models, with applications to social, biological and environmental problems, (1976), Prentice-Hall Englewood Cliffs, NJ · Zbl 0363.90002
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.