AN NC ALGORITHM FOR THE CLIQUE COVER PROBLEM IN COCOMPARABILITY GRAPHS AND ITS APPLICATION

Authors
RHEE CK LIANG YD
Citation
Ck. Rhee et Yd. Liang, AN NC ALGORITHM FOR THE CLIQUE COVER PROBLEM IN COCOMPARABILITY GRAPHS AND ITS APPLICATION, Information processing letters, 57(5), 1996, pp. 287-290
Citations number
7
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
57
Issue
5
Year of publication
1996
Pages
287 - 290
Database
ISI
SICI code
0020-0190(1996)57:5<287:ANAFTC>2.0.ZU;2-H
Abstract
In this paper, we present an extremely simple NC algorithm for finding a minimum clique cover in a cocomparability graph. Our algorithm take s O(log n) time using O(n(3+epsilon)) processors on the CRCW PRAM, whe re n is the number of vertices. It is also shown that this algorithm c an be applied to solve in parallel the depth-first search problem for permutation graphs. The best known DFS algorithm for the permutation g raphs runs in O(log(2) n) time on a CRCW PRAM model.