SUCCINCT REPRESENTATION OF GENERAL UNLABELED GRAPHS

被引:35
作者
NAOR, M
机构
[1] IBM Almaden Research Center, San Jose, CA 95120
基金
美国国家科学基金会;
关键词
D O I
10.1016/0166-218X(90)90011-Z
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We show that general unlabeled graphs on n nodes can be represented by (n2) - n log2 n + O(n) bits which is optimal up to the O(n) term. Both the encoding and decoding require linear time. © 1990.
引用
收藏
页码:303 / 307
页数:5
相关论文
共 8 条
[1]  
DEVROY, 1986, NONUNIFORM RANDOM VA
[2]  
FIAT A, 1988, 20TH P ACM S THEOR C, P367
[3]  
FIAT A, 1989, 21ST P ACM S THEOR C, P336
[4]  
FIAT A, 1988, 20TH ANN ACM S THEOR, P344
[5]  
GOLDBERG A, 1985, 17TH P ACM S THEOR C, P440
[6]  
Graham R. L., 1980, RAMSEY THEORY
[7]  
Harary F., 1973, GRAPHICAL ENUMERATIO
[8]   ON THE SUCCINCT REPRESENTATION OF GRAPHS [J].
TURAN, G .
DISCRETE APPLIED MATHEMATICS, 1984, 8 (03) :289-294