An NC Algorithm for the Clique Cover Problem in Cocomparability Graphs and its Application

Chongkye Rhee; Y. Daniel Liang

doi:10.1016/0020-0190(95)00206-5

An NC Algorithm for the Clique Cover Problem in Cocomparability Graphs and its Application

Chongkye Rhee
, Y. Daniel Liang

Computer Science

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

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 + ε ) 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.

Original language	American English
Journal	Information Processing Letters
Volume	57
DOIs	https://doi.org/10.1016/0020-0190(95)00206-5
State	Published - Mar 11 1996

Disciplines

Computer Sciences

Keywords

Cocomparability graphs
Depth-first search
Minimum clique cover
Permutation graphs

Access to Document

10.1016/0020-0190(95)00206-5License: Unspecified

Cite this

@article{d7d7931bea35400ab2713b9ff4f5c1f4,

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 + ε ) 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. ",

keywords = "Cocomparability graphs, Depth-first search, Minimum clique cover, Permutation graphs",

author = "Chongkye Rhee and Liang, \{Y. Daniel\}",

note = "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) processors on the CRCW PRAM, where n is the number of vertices.",

year = "1996",

month = mar,

day = "11",

doi = "10.1016/0020-0190(95)00206-5",

language = "American English",

volume = "57",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - An NC Algorithm for the Clique Cover Problem in Cocomparability Graphs and its Application

AU - Rhee, Chongkye

AU - Liang, Y. Daniel

N1 - 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) processors on the CRCW PRAM, where n is the number of vertices.

PY - 1996/3/11

Y1 - 1996/3/11

N2 - 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 + ε ) 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.

AB - 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 + ε ) 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.

KW - Cocomparability graphs

KW - Depth-first search

KW - Minimum clique cover

KW - Permutation graphs

UR - https://www.sciencedirect.com/science/article/abs/pii/0020019095002065

U2 - 10.1016/0020-0190(95)00206-5

DO - 10.1016/0020-0190(95)00206-5

M3 - Article

SN - 0020-0190

VL - 57

JO - Information Processing Letters

JF - Information Processing Letters

ER -

An NC Algorithm for the Clique Cover Problem in Cocomparability Graphs and its Application

Abstract

Disciplines

Keywords

Access to Document

Other files and links

Fingerprint

Cite this