Language:

Succinct Representation of Labeled Graphs

Algorithmica, 2012-02, Vol.62 (1-2), p.224-257 [Peer Reviewed Journal]

Springer Science+Business Media, LLC 2010 ;2015 INIST-CNRS ;Distributed under a Creative Commons Attribution 4.0 International License ;ISSN: 0178-4617 ;EISSN: 1432-0541 ;DOI: 10.1007/s00453-010-9452-7

Full text available

Citations Cited by

Actions
1. Add to My Research
2. Remove from My Research
3. E-mail
4. Print
5. Permalink
6. Citation
7. EasyBib
8. EndNote
9. RefWorks
10. Delicious
11. Export RIS
12. Export BibTeX

Title:
Succinct Representation of Labeled Graphs
Author: Barbay, Jérémy ; Castelli Aleardi, Luca ; He, Meng ; Munro, J. Ian
Subjects: Algorithm Analysis and Problem Complexity ; Algorithmics. Computability. Computer arithmetics ; Algorithms ; Applied sciences ; Combinatorics ; Combinatorics. Ordered structures ; Computational Geometry ; Computer Science ; Computer science; control theory; systems ; Computer Systems Organization and Communication Networks ; Data Structures and Information Theory ; Exact sciences and technology ; Graph theory ; Information retrieval. Graph ; Mathematics ; Mathematics of Computing ; Sciences and techniques of general use ; Theoretical computing ; Theory of Computation
Is Part Of: Algorithmica, 2012-02, Vol.62 (1-2), p.224-257
Description: 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 (counter clockwise) 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, while previous work uses O ( k ) time.
Publisher: New York: Springer-Verlag
Language: English
Identifier: ISSN: 0178-4617
EISSN: 1432-0541
DOI: 10.1007/s00453-010-9452-7
Source: Hyper Article en Ligne (HAL) (Open Access)
Alma/SFX Local Collection

Back to results list


INSPIRE LIBRARY - TON DUC THANG UNIVERSITY	(84-028) 37 755 057	Feedback
19 Nguyen Huu Tho St. Dist.7, HCM	thuvien@tdtu.edu.vn	Feedback

Succinct Representation of Labeled Graphs

Springer Science+Business Media, LLC 2010 ;2015 INIST-CNRS ;Distributed under a Creative Commons Attribution 4.0 International License ;ISSN: 0178-4617 ;EISSN: 1432-0541 ;DOI: 10.1007/s00453-010-9452-7

Searching Remote Databases, Please Wait