TY - JOUR
AU - Lopes, Juan P. A.
AU - Oliveira, Fabiano de S.
AU - Pinto, Paulo E. D.
PY - 2017
TI - Representações Implícitas Probabilísticas de Grafos
JF - Anais do Encontro de Teoria da Computação (ETC); 2017: Anais do II Encontro de Teoria da Computação
DO - 10.5753/etc.2017.3179
KW -
N2 - This paper introduces the concept of probabilistic implicit graph representations, extending the definition from [Spinrad 2003] by allowing the adjacency test to have a constant probability of false positives or false negatives. It also discusses two novel representations based on well-known probabilistic data structures: one that uses Bloom filters and can represent general graphs with the same space complexity as the adjacency matrix (but outperforms it for sparse graphs), and other that uses MinHash and can represent trees with lower space complexity than any deterministic implicit representation.
UR - https://sol.sbc.org.br/index.php/etc/article/view/3179