CLIQUE TRANSVERSAL AND CLIQUE INDEPENDENCE ON COMPARABILITY-GRAPHS

Authors
BALACHANDRAN V NAGAVAMSI P RANGAN CP
Citation
V. Balachandran et al., CLIQUE TRANSVERSAL AND CLIQUE INDEPENDENCE ON COMPARABILITY-GRAPHS, Information processing letters, 58(4), 1996, pp. 181-184
Citations number
11
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
58
Issue
4
Year of publication
1996
Pages
181 - 184
Database
ISI
SICI code
0020-0190(1996)58:4<181:CTACIO>2.0.ZU;2-P
Abstract
We present O(m root n + M(n)) algorithms for finding the clique transv ersal number and the clique independence number for a comparability gr aph of n nodes, where M(n) is the complexity of multiplying two n x n matrices.