Simple and efficient graph compression schemes for dense and complement graphs

Ming Yang Kao; Shang Hua Teng

doi:10.1007/3-540-58325-4_211

Simple and efficient graph compression schemes for dense and complement graphs

Ming Yang Kao, Shang Hua Teng

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings
Editors	Ding-Zhu Du, Ding-Zhu Du, Xiang-Sun Zhang
Publisher	Springer Verlag
Pages	451-459
Number of pages	9
ISBN (Print)	9783540583257
DOIs	https://doi.org/10.1007/3-540-58325-4_211
State	Published - 1994
Event	5th Annual International Symposium on Algorithms and Computation, ISAAC 1994 - Beijing, China Duration: Aug 25 1994 → Aug 27 1994

Publication series

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

Other

Other	5th Annual International Symposium on Algorithms and Computation, ISAAC 1994
Country/Territory	China
City	Beijing
Period	8/25/94 → 8/27/94

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-58325-4_211

Cite this

Kao, M. Y., & Teng, S. H. (1994). Simple and efficient graph compression schemes for dense and complement graphs. In D.-Z. Du, D.-Z. Du, & X.-S. Zhang (Eds.), Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings (pp. 451-459). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 834 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-58325-4_211

Kao, Ming Yang ; Teng, Shang Hua. / Simple and efficient graph compression schemes for dense and complement graphs. Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings. editor / Ding-Zhu Du ; Ding-Zhu Du ; Xiang-Sun Zhang . Springer Verlag, 1994. pp. 451-459 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7575c23ab9ba4dc890f009af1c148f3a,

title = "Simple and efficient graph compression schemes for dense and complement graphs",

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

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

note = "Funding Information: Supported in part by NSF Grant CCR-9101385. Supported in part by AFOSR F49620-92-J-0125 and Darpa N00014-92-J-1799. Funding Information: We develop two new approaches that first compute succinct representations of G c from the given linked-list representation of G. Using simple data structures, we can efficiently manipulate these smaller representations of G c to compute its connected components. When m =: o(n 2) but m = ~2(lo--~) n 2 , one of our approaches computes the connected components of G ~ in the optimal O(rn) time. When m = O(lo--~), n ~ our other approach computes the desired components *Department of Computer Science, Duke University, Durham, NC 27706. Supported in part by NSF Grant CCR-9101385. tDepartment of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139. Supported in part by AFOSR F49620-92-J-0125 and Darpa N00014-92-J-1799. Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; 5th Annual International Symposium on Algorithms and Computation, ISAAC 1994 ; Conference date: 25-08-1994 Through 27-08-1994",

year = "1994",

doi = "10.1007/3-540-58325-4_211",

language = "English (US)",

isbn = "9783540583257",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "451--459",

editor = "Ding-Zhu Du and Ding-Zhu Du and {Zhang }, Xiang-Sun",

booktitle = "Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings",

}

Kao, MY & Teng, SH 1994, Simple and efficient graph compression schemes for dense and complement graphs. in D-Z Du, D-Z Du & X-S Zhang (eds), Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 834 LNCS, Springer Verlag, pp. 451-459, 5th Annual International Symposium on Algorithms and Computation, ISAAC 1994, Beijing, China, 8/25/94. https://doi.org/10.1007/3-540-58325-4_211

Simple and efficient graph compression schemes for dense and complement graphs. / Kao, Ming Yang; Teng, Shang Hua.
Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings. ed. / Ding-Zhu Du; Ding-Zhu Du; Xiang-Sun Zhang . Springer Verlag, 1994. p. 451-459 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 834 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Simple and efficient graph compression schemes for dense and complement graphs

AU - Kao, Ming Yang

AU - Teng, Shang Hua

N1 - Funding Information: Supported in part by NSF Grant CCR-9101385. Supported in part by AFOSR F49620-92-J-0125 and Darpa N00014-92-J-1799. Funding Information: We develop two new approaches that first compute succinct representations of G c from the given linked-list representation of G. Using simple data structures, we can efficiently manipulate these smaller representations of G c to compute its connected components. When m =: o(n 2) but m = ~2(lo--~) n 2 , one of our approaches computes the connected components of G ~ in the optimal O(rn) time. When m = O(lo--~), n ~ our other approach computes the desired components *Department of Computer Science, Duke University, Durham, NC 27706. Supported in part by NSF Grant CCR-9101385. tDepartment of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139. Supported in part by AFOSR F49620-92-J-0125 and Darpa N00014-92-J-1799. Publisher Copyright: © 1994, Springer Verlag. All rights reserved.

PY - 1994

Y1 - 1994

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

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

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

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

U2 - 10.1007/3-540-58325-4_211

DO - 10.1007/3-540-58325-4_211

M3 - Conference contribution

AN - SCOPUS:0041775994

SN - 9783540583257

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 451

EP - 459

BT - Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings

A2 - Du, Ding-Zhu

A2 - Zhang , Xiang-Sun

PB - Springer Verlag

T2 - 5th Annual International Symposium on Algorithms and Computation, ISAAC 1994

Y2 - 25 August 1994 through 27 August 1994

ER -

Kao MY, Teng SH. Simple and efficient graph compression schemes for dense and complement graphs. In Du DZ, Du DZ, Zhang XS, editors, Algorithms and Computation - 5th International Symposium, ISAAC 1994, Proceedings. Springer Verlag. 1994. p. 451-459. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-58325-4_211

Simple and efficient graph compression schemes for dense and complement graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this