Succinct Representation of Labeled Graphs

Abstract : In many applications, the properties of an object being modeled are stored as labels on vertices or edges of a graph. In this paper, we consider succinct representation of labeled graphs. Our main results are the succinct representations of labeled and multi-labeled graphs (we consider planar triangulations, planar graphs and $k$-page graphs) to support various label queries efficiently. The additional space cost to store the labels is essentially the information-theoretic minimum. As far as we know, our representations are the first succinct representations of labeled graphs. We also have two preliminary results to achieve the main contribution. First, we design a succinct representation of unlabeled planar triangulations to support the rank/select of edges in ccw (counterclockwise) order in addition to the other operations supported in previous work. Second, we design a succinct representation for a $k$-page graph when $k$ is large to support various navigational operations more efficiently. In particular, we can test the adjacency of two vertices in $O(\lg k)$ time\footnote{We use $\log_2 x$ to denote the logarithmic base $2$ and $\lg x$ to denote $\lceil\log_2 x\rceil$. Occasionally this matters.}, while previous work uses $O(k)$ time.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2012, 62 (1-2), pp.224-257. 〈10.1007/s00453-010-9452-7〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00712915
Contributeur : Luca Castelli Aleardi <>
Soumis le : jeudi 28 juin 2012 - 15:06:40
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : samedi 29 septembre 2012 - 02:25:47

Fichier

SuccinctLabeledGraphs_Algorith...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jérémy Barbay, Luca Castelli Aleardi, Meng He, Ian Munro. Succinct Representation of Labeled Graphs. Algorithmica, Springer Verlag, 2012, 62 (1-2), pp.224-257. 〈10.1007/s00453-010-9452-7〉. 〈hal-00712915〉

Partager

Métriques

Consultations de la notice

335

Téléchargements de fichiers

427