Graph compression by BFS

DOI10.3390/A2031031zbMath1461.68021OpenAlexW2018900730MaRDI QIDQ1662490

Guido Drovandi, Alberto Apostolico

Publication date: 20 August 2018

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a2031031

zbMATH Keywords

data compressionbreadth-first searchgraph compressionweb graphuniversal codes

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Information storage and retrieval of data (68P20) Internet topics (68M11)

Related Items (8)

Linearity is strictly more powerful than contiguity for encoding graphs ⋮ Linearity Is Strictly More Powerful Than Contiguity for Encoding Graphs ⋮ Tight and simple web graph compression for forward and reverse neighbor queries ⋮ Fast Construction of Compressed Web Graphs ⋮ Multiscale approach for the network compression-friendly ordering ⋮ Fast and compact planar embeddings ⋮ Summarizing and understanding large graphs ⋮ Compact structure for sparse undirected graphs based on a clique graph partition

Uses Software

• UbiCrawler

Cites Work

• On the succinct representation of graphs
• Clique partitions, graph compression and speeding-up algorithms
• Efficient Compression of Web Graphs
• Universal codeword sets and representations of the integers
• Efficient Storage and Retrieval by Content and Address of Static Files
• Speeding Up Algorithms on Compressed Web Graphs
• Codes for the World Wide Web

This page was built for publication: Graph compression by BFS