Compact structure for sparse undirected graphs based on a clique graph partition

DOI10.1016/j.ins.2020.09.010zbMath1475.68243OpenAlexW3087053539MaRDI QIDQ2054100

Susana Ladra, Gonzalo Navarro, Lilian Salinas, Cecilia Hernández, Felipe Glaria

Publication date: 30 November 2021

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2020.09.010

zbMATH Keywords

clusteringmaximal cliquesnetwork analysisgraph compressioncompact data structures

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Data structures (68P05)

Related Items (4)

MIP formulations for induced graph optimization problems: a tutorial ⋮ Iterated multilevel simulated annealing for large-scale graph conductance minimization ⋮ The minimum quasi-clique partitioning problem: complexity, formulations, and a computational study ⋮ Efficient game theoretic approach to dynamic graph partitioning

Uses Software

• WebGraph

Cites Work

• Graph compression by BFS
• A characterization of clique graphs
• Efficient Compression of Web Graphs
• Extended Compact Web Graph Representations
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Listing All Maximal Cliques in Large Sparse Real-World Graphs
• Algorithm Theory - SWAT 2004
• A Method for the Construction of Minimum-Redundancy Codes
• A partial characterization of clique graphs

This page was built for publication: Compact structure for sparse undirected graphs based on a clique graph partition