Name
Title | ||
|---|---|---|
An NC algorithm for the clique cover problem in cocomparability graphs and its application |
Abstract | ||
|---|---|---|
In this paper, we present an extremely simple NC algorithm for finding a minimum clique cover in a cocomparability graph. Our algorithm takes O(log n) time using O(n(3+epsilon)) processors on the CRCW PRAM, where n is the number of vertices. It is also shown that this algorithm can be applied to solve in parallel the depth-first search problem for permutation graphs. The best known DFS algorithm for the permutation graphs runs in O(log(2) n) time on a CRCW PRAM model. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1016/0020-0190(95)00206-5 | Inf. Process. Lett. |
Keywords | Field | DocType |
cocomparability graph,nc algorithm,clique cover problem,depth first search,permutation graph | Graph theory,Permutation graph,Discrete mathematics,Combinatorics,Vertex (geometry),Chordal graph,Permutation,Breadth-first search,Algorithm,Clique cover,Clique (graph theory),Mathematics | Journal |
Volume | Issue | ISSN |
57 | 5 | 0020-0190 |
Citations | PageRank | References |
1 | 0.40 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chongkye Rhee | 1 | 20 | 3.39 |
| Y. Daniel Liang | 2 | 153 | 14.93 |