On Dynamic Succinct Graph Representations
Miguel Coimbra, Alexandre Francisco, Luís Russo, Guillermo de
Bernardo, Susana Ladra, and Gonzalo Navarro
We address the problem of representing dynamic graphs using k^2-trees.
The k^2-tree data structure is one of the succinct data structures
proposed for representing static graphs, and binary relations in general. It
relies on compact representations of bit vectors. Hence, by relying on compact
representations of dynamic bit vectors, we can also represent dynamic
graphs. In this paper we follow instead the ideas by Munro et al., and we
present an alternative implementation for representing dynamic graphs using
k^2-trees. Our experimental
results show that this new implementation is competitive in practice.