Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Trading uninitialized space for time

Autor
Valiente, G.
Tipus d'activitat
Article en revista
Revista
Information processing letters
Data de publicació
2004-10-16
Volum
92
Número
1
Pàgina inicial
9
Pàgina final
13
DOI
https://doi.org/10.1016/j.ipl.2004.06.002 Obrir en finestra nova
URL
http://www.sciencedirect.com/science/article/pii/S0020019004001814 Obrir en finestra nova
Resum
The design of efficient graph algorithms usually precludes the test of edge existence, because an efficient support of that operation already requires time O(n2) for the initialization of an adjacency-matrix representation. We describe an alternative representation of static directed graphs taking T(n+m) initialization time and using T(n2) space, which supports the efficient implementation of all usual operations on static graphs. The sparse graph representation allows the design of efficient gr...
Paraules clau
Algorithms, Analysis of algorithms, Data structures, Design of algorithms, Graph algorithms
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants