Parallel algorithms for recognizing P5-free and P¯5-free weakly chordal graphs

作     者：Nikolopoulos, Stavros D. Palios, Leonidas 

作者机构：Department of Computer Science University of Ioannina P.O. Box 1186 GR-45110 Ioannina Greece 

出 版 物：《Parallel Processing Letters》 (Parallel Process Lett)

年 卷 期：2004年第14卷第1期

页      面：119-129页

核心收录：

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Parallel algorithms 

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