Simple and efficient graph compression schemes for dense and complement graphs

Ming Yang Kao, Shang Hua Teng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

In this paper, 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)
Title of host publicationAlgorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings
EditorsDing-Zhu Du, Ding-Zhu Du, Xiang-Sun Zhang
PublisherSpringer Verlag
Pages451-459
Number of pages9
ISBN (Print)9783540583257
DOIs
StatePublished - 1994
Event5th Annual International Symposium on Algorithms and Computation, ISAAC 1994 - Beijing, China
Duration: Aug 25 1994Aug 27 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume834 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other5th Annual International Symposium on Algorithms and Computation, ISAAC 1994
CountryChina
CityBeijing
Period8/25/948/27/94

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint 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