How to represent a graph in memory is a fundamental data-structuring problem. In the usual representations, a graph is stored by representing explicitly all vertices and all edges. The names (labels) assigned to vertices are used only to encode the edges and reveal nothing about the structure of the graph itself and hence are a "waste" of space. In this context, we present a general framework for labeling any graph so that adjacency between any two given vertices can be tested in constant time. The labeling scheme assigns to each vertex x a O(delta (x) log(2) n) bit label, where n is the number of vertices and delta (x) is x's degree. The adjacency test can be performed in seven steps and the scheme can be computed in polynomial time. The proposed graph encoding positively demonstrates its superiority over the usual representations, i.e. adjacency matrix and adjacency list representations, which require O(n log n) bit label per vertex and constant time adjacency test, and O(delta (x)log n) bit label per vertex and O(log delta (x)) steps to test adjacency, respectively. Additionally, the labeling scheme is implicit, that is: no pointers are used. (C) 2001 Elsevier Science B.V. All rights reserved.

Talamo, M., Vocca, P. (2001). Representing graphs implicitly using almost optimal space. In Discrete Applied Mathematics (pp.193-210). AMSTERDAM : ELSEVIER SCIENCE BV [10.1016/S0166-218X(00)00225-0].

Representing graphs implicitly using almost optimal space

TALAMO, MAURIZIO;Vocca, P.
2001-01-01

Abstract

How to represent a graph in memory is a fundamental data-structuring problem. In the usual representations, a graph is stored by representing explicitly all vertices and all edges. The names (labels) assigned to vertices are used only to encode the edges and reveal nothing about the structure of the graph itself and hence are a "waste" of space. In this context, we present a general framework for labeling any graph so that adjacency between any two given vertices can be tested in constant time. The labeling scheme assigns to each vertex x a O(delta (x) log(2) n) bit label, where n is the number of vertices and delta (x) is x's degree. The adjacency test can be performed in seven steps and the scheme can be computed in polynomial time. The proposed graph encoding positively demonstrates its superiority over the usual representations, i.e. adjacency matrix and adjacency list representations, which require O(n log n) bit label per vertex and constant time adjacency test, and O(delta (x)log n) bit label per vertex and O(log delta (x)) steps to test adjacency, respectively. Additionally, the labeling scheme is implicit, that is: no pointers are used. (C) 2001 Elsevier Science B.V. All rights reserved.
24th International Workshop on Graph-Theoretic Concepts in Computer Science (WG '98)
JUN 18-20, 1998
Slovak Acad Comp Sci, RWTH Aachen, Dept Comp Sci, Slovak Soc Comp Sci
Rilevanza internazionale
2001
Settore INF/01 - INFORMATICA
English
SUCCINCT REPRESENTATIONS; ROUTING TABLES; NETWORKS; SEARCH; TIME
Intervento a convegno
Talamo, M., Vocca, P. (2001). Representing graphs implicitly using almost optimal space. In Discrete Applied Mathematics (pp.193-210). AMSTERDAM : ELSEVIER SCIENCE BV [10.1016/S0166-218X(00)00225-0].
Talamo, M; Vocca, P
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/41899
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 9
social impact