Clique transversal and clique independence on comparability graphs

被引：43
作者：
Balachandran, V
Nagavamsi, P
Rangan, CP
机构：
[1] Indian Institute of Technology
[2] Theor. Computer Science Laboratory, Dept. of Comp. Sci. and Engineering, Indian Institute of Technology
来源：
INFORMATION PROCESSING LETTERS | 1996年 / 58卷 / 04期
关键词：
algorithms; clique transversal; clique independence;
D O I：
10.1016/0020-0190(96)00054-3
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We present O(m root n + M(n)) algorithms for finding the clique transversal number and the clique independence number for a comparability graph of n nodes, where M(n) is the complexity of multiplying two n x n matrices.
引用
收藏
页码：181 / 184
页数：4
相关论文
共 11 条
[1]  
Aho A.V., 1974, The Design and Analysis of Computer Algorithms
[2]   CLIQUE-TRANSVERSAL SETS OF LINE GRAPHS AND COMPLEMENTS OF LINE GRAPHS [J].
ANDREAE, T ;
SCHUGHART, M ;
TUZA, Z .
DISCRETE MATHEMATICS, 1991, 88 (01) :11-20
[3]  
BONDY JA, 1976, GRAPH THEORY APPLICA
[4]   ALGORITHMIC ASPECTS OF NEIGHBORHOOD NUMBERS [J].
CHANG, GJ ;
FARBER, M ;
TUZA, Z .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1993, 6 (01) :24-29
[5]  
Even S., 1979, Graph Algorithms
[6]  
Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs
[7]  
Liu C. L., 1985, ELEMENTS DISCRETE MA
[8]  
Menger K, 1927, FUND MATH, V10, P96, DOI DOI 10.4064/FM-10-1-96-115
[9]  
Redei L., 1934, Acta Litt. Szeged, V7, P39
[10]  
SPINRAD J, 1983, 15TH P ANN ACM S THE, P457
12