Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs

Ming Yang Kao*, Neill Occhiogrosso, Shang Hua Teng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We present two graph compression schemes for solving problems on dense graphs and complement graphs. They compress a graph or its complement graph into two kinds of succinct representations based on adjacency intervals and adjacency integers, respectively. These two schemes complement each other for different ranges of density. Using these schemes, we develop optimal or near optimal algorithms for fundamental graph problems. In contrast to previous graph compression schemes, ours are simple and efficient for practical applications.

Original languageEnglish (US)
Pages (from-to)351-359
Number of pages9
JournalJournal of Combinatorial Optimization
Issue number4
StatePublished - 1998

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs'. Together they form a unique fingerprint.

Cite this