Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs

Ming Yang Kao; Neill Occhiogrosso; Shang Hua Teng

doi:10.1023/A:1009720402326

Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs

Ming Yang Kao^*, Neill Occhiogrosso, Shang Hua Teng

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	351-359
Number of pages	9
Journal	Journal of Combinatorial Optimization
Volume	2
Issue number	4
DOIs	https://doi.org/10.1023/A:1009720402326
State	Published - 1998

ASJC Scopus subject areas

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

Access to Document

10.1023/A:1009720402326

Cite this

@article{e623e77a2e6a452394b8d3691272d282,

title = "Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs",

abstract = "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.",

author = "Kao, {Ming Yang} and Neill Occhiogrosso and Teng, {Shang Hua}",

note = "Funding Information: ⁄A preliminary version of this work appeared in D.Z. Du and X.S. Zhang, editors, Lecture Notes in Computer Science 834: Proceedings of the 5th International Symposium on Algorithms and Computation, pages 201–210, Springer-Verlag, New York, 1994. ⁄⁄Research supported in part by NSF Grant CCR-9531028. †Supported in part by an NSF CAREER award (CCR-9502540) and an Alfred P. Sloan Research Fellowship. Work performed while this author was with Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139.",

year = "1998",

doi = "10.1023/A:1009720402326",

language = "English (US)",

volume = "2",

pages = "351--359",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs

AU - Kao, Ming Yang

AU - Occhiogrosso, Neill

AU - Teng, Shang Hua

N1 - Funding Information: ⁄A preliminary version of this work appeared in D.Z. Du and X.S. Zhang, editors, Lecture Notes in Computer Science 834: Proceedings of the 5th International Symposium on Algorithms and Computation, pages 201–210, Springer-Verlag, New York, 1994. ⁄⁄Research supported in part by NSF Grant CCR-9531028. †Supported in part by an NSF CAREER award (CCR-9502540) and an Alfred P. Sloan Research Fellowship. Work performed while this author was with Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139.

PY - 1998

Y1 - 1998

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=2342617674&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=2342617674&partnerID=8YFLogxK

U2 - 10.1023/A:1009720402326

DO - 10.1023/A:1009720402326

M3 - Article

AN - SCOPUS:2342617674

SN - 1382-6905

VL - 2

SP - 351

EP - 359

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this