SUCCINCT REPRESENTATION OF GENERAL UNLABELED GRAPHS

被引：35
作者：
NAOR, M
机构：
[1] IBM Almaden Research Center, San Jose, CA 95120
来源：
DISCRETE APPLIED MATHEMATICS | 1990年 / 28卷 / 03期
基金：
美国国家科学基金会;
关键词：
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
    TURAN, G
    [J]. DISCRETE APPLIED MATHEMATICS, 1984, 8 (03) : 289 - 294
1