CLIQUE COVERING AND CLIQUE PARTITION IN GENERALIZATIONS OF LINE GRAPHS

被引：3
作者：
PRISNER, E
机构：
[1] Mathematisches Seminar, Universität Hamburg, 20146 Hamburg
来源：
DISCRETE APPLIED MATHEMATICS | 1995年 / 56卷 / 01期
关键词：
D O I：
10.1016/0166-218X(94)00076-P
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Cliques are complete subgraphs of a graph. In this note we show that minimum sets of maximal cliques covering, respectively partitioning the edge set of a graph can be computed efficiently for certain superclasses of the class of line graphs.
引用
收藏
页码：93 / 98
页数：6
相关论文
共 11 条
[1]   THE NP-COMPLETENESS OF SOME EDGE-PARTITION PROBLEMS [J].
HOLYER, I .
SIAM JOURNAL ON COMPUTING, 1981, 10 (04) :713-717
[2]  
Hopcroft J. E., 1973, SIAM Journal on Computing, V2, P225, DOI 10.1137/0202019
[3]  
LE VB, UNPUB FACET GRAPHS P
[4]  
ORLIN J, 1977, INDAG MATH, V39, P406
[5]   CLIQUE COVERING OF GRAPHS .5. ALGORITHMS [J].
PULLMAN, NJ .
SIAM JOURNAL ON COMPUTING, 1984, 13 (01) :57-75
[6]  
PULLMAN NJ, 1982, 10TH P AUSTR C COMB
[7]   APPLICATIONS OF EDGE COVERINGS BY CLIQUES [J].
ROBERTS, FS .
DISCRETE APPLIED MATHEMATICS, 1985, 10 (01) :93-109
[8]   ON THE TREE-REPRESENTATION OF CHORDAL GRAPHS [J].
SHIBATA, Y .
JOURNAL OF GRAPH THEORY, 1988, 12 (03) :421-428
[9]  
Tsukiyama S., 1977, SIAM Journal on Computing, V6, P505, DOI 10.1137/0206036
[10]  
Wallis W.D., 1990, J COMBIN MATH COMBIN, V8, P187
12