Simple and Efficient Graph Compression Schemes for Dense and Complement Graphs |
| |
| Authors: | Ming-Yang Kao Neill Occhiogrosso Shang-Hua Teng |
| |
| Institution: | (1) Department of Computer Science, Yale University, New Haven, CT, 06520;(2) Department of Computer Science, Duke University, Durham, NC, 27708;(3) Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, 61801;(4) Department of Computer Science, University of Minnesota, Minneapolis, MN, 55455 |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
