No Access

Parallel Algorithms for Recognizing P₅-free and -free Weakly Chordal Graphs

Stavros D. Nikolopoulos

Department of Computer Science, University of Ioannina, P.O.Box 1186, GR-45110 Ioannina, Greece

Search for more papers by this author

and

Leonidas Palios

Department of Computer Science, University of Ioannina, P.O.Box 1186, GR-45110 Ioannina, Greece

Search for more papers by this author

https://doi.org/10.1142/S0129626404001763Cited by:0 (Source: Crossref)

Abstract

We prove algorithmic characterizations of weakly chordal graphs, which lead to efficient parallel algorithms for recognizing P₅-free and -free weakly chordal graphs. For an input graph on n vertices and m edges, our algorithms run in O(log²n) time and require O(m²/log n) processors on the EREW PRAM model of computation. The proposed recognition algorithms efficiently detect P₅s and in weakly chordal graphs in O(log n) time with O(m²/logn) processors on the EREW PRAM. Additionally, we show how the algorithms can be augmented to provide a certificate for the existence of a P₅ (or a ) in case the input graph is not P₅-free (respectively, -free) weakly chordal.

Keywords:

References

S. G. Akl , Parallel Computation: Models and Methods ( Prentice Hall , 1997 ) . Google Scholar
S. Arikati and P. Rangan, Discrete Applied Math. 31, 71 (1991), DOI: 10.1016/0166-218X(91)90033-S. Crossref, Web of Science, Google Scholar
C. Beeriet al., J. Assoc. Comput. Machinery 30, 479 (1983). Crossref, Web of Science, Google Scholar
A. Berry, J.-P. Bordat and P. Heggernes, Nordic. J. Computing 7, 164 (2000). Web of Science, Google Scholar
N. Chandrasekharan, V. S. Lakshmanan and M. Medidi, Parallel Process. Letters 3, 165 (1993), DOI: 10.1142/S0129626493000204. Link, Web of Science, Google Scholar
K. W. Chong, S. D. Nikolopoulos, and L. Palios, An optimal parallel co-connectivity algorithm, Theory of Computing Systems (to appear) . Google Scholar
V. Chvátal, Annals of Discrete Math. 21, 63 (1984). Google Scholar
V. Chvátal, A class of perfectly orderable graphs, Report 89-573-OR, Forschungsinstitut für Diskrete Mathematik, Bonn, 1989 . Google Scholar
E. Dahlhaus, Discrete Appl. Math. 57, 29 (1995), DOI: 10.1016/0166-218X(93)E0138-O. Crossref, Web of Science, Google Scholar
M. C. Golumbic , Algorithmic Graph Theory and Perfect Graphs ( Academic Press , New York , 1980 ) . Google Scholar
R. B. Hayward, J. Comb. Theory B 39, 200 (1985), DOI: 10.1016/0095-8956(85)90050-4. Crossref, Web of Science, Google Scholar
R. B. Hayward, Two classes of perfect graphs, PhD Thesis, School of Computer Science, McGill University, 1987 . Google Scholar
R. B. Hayward, Discrete Applied Math. 73, 199 (1997), DOI: 10.1016/S0166-218X(96)00008-X. Crossref, Web of Science, Google Scholar
R. B. Hayward, C. Hoàng and F. Maffray, Graphs and Combinatorics 5, 339 (1989), DOI: 10.1007/BF01788689. Crossref, Web of Science, Google Scholar
R. B. Hayward, J. Spinrad and R. Sritharan, Weakly chordal graph algorithms via handles, Proc. 11th ACM-SIAM Symp. on Discrete Algorithms (SODA'00) (2000) pp. 42–49. Google Scholar
X. He, J. Algorithms 15, 284 (1993), DOI: 10.1006/jagm.1993.1042. Crossref, Web of Science, Google Scholar
C. T. Hoàng, Discrete Applied Math. 66, 219 (1996). Crossref, Web of Science, Google Scholar
C. T. Hoànget al., Discrete Math. 102, 67 (1992). Crossref, Web of Science, Google Scholar
J. Jájá , An Introduction to Parallel Algorithms ( Addison-Wesley , 1992 ) . Google Scholar
H. Lerchs, On Cliques and Kernels, Technical Report, Department of Computer Science, University of Toronto, 1971 . Google Scholar
S. D. Nikolopoulos and L. Palios , Hole and antihole detection in graphs , Proc. 15th ACM-SIAM Symp. on Discrete Algorithms (SODA'04) ( 2004 ) . Google Scholar
D. J. Rose, J. Math. Anal. Applications 32, 597 (1970), DOI: 10.1016/0022-247X(70)90282-9. Crossref, Web of Science, Google Scholar
J. P. Spinrad, Inform. Process. Letters 39, 227 (1991), DOI: 10.1016/0020-0190(91)90184-J. Crossref, Web of Science, Google Scholar
J. P. Spinrad and R. Sritharan, Discrete Applied Math. 59, 181 (1995), DOI: 10.1016/0166-218X(93)E0161-Q. Crossref, Web of Science, Google Scholar