Simple and efficient graph compression schemes for dense and complement graphs

Citation
My. Kao et al., Simple and efficient graph compression schemes for dense and complement graphs, J COMB OPTI, 2(4), 1999, pp. 351-359
Citations number
19
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics,"Engineering Mathematics
Journal title
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN journal
1382-6905 → ACNP
Volume
2
Issue
4
Year of publication
1999
Pages
351 - 359
Database
ISI
SICI code
1382-6905(1999)2:4<351:SAEGCS>2.0.ZU;2-V
Abstract
We present two graph compression schemes for solving problems on dense grap hs and complement graphs. They compress a graph or its complement graph int o two kinds of succinct representations based on adjacency intervals and ad jacency integers, respectively. These two schemes complement each other for different ranges of density. Using these schemes, we develop optimal or ne ar optimal algorithms for fundamental graph problems. In contrast to previo us graph compression schemes, ours are simple and efficient for practical a pplications.