Given a series G = {G(0), G(1),...,G(T)} of graphs encompassing V vertices and E edges. a periodic graph is a spatially as well as temporally maximal subgraph of a subsequence of G in the form G(i)(p) = {G(i), G(i+p),...,G(i+np)), where n is not smaller than some predetermined threshold value sigma. An algorithm for finding all such subgraphs is proposed taking time O((E + V)T(2) In(T/sigma)), which is faster by a factor of T than the method previously available.
Speedup for a Periodic Subgraph Miner
APOSTOLICO, ALBERTO;PIZZI, CINZIA
2011
Abstract
Given a series G = {G(0), G(1),...,G(T)} of graphs encompassing V vertices and E edges. a periodic graph is a spatially as well as temporally maximal subgraph of a subsequence of G in the form G(i)(p) = {G(i), G(i+p),...,G(i+np)), where n is not smaller than some predetermined threshold value sigma. An algorithm for finding all such subgraphs is proposed taking time O((E + V)T(2) In(T/sigma)), which is faster by a factor of T than the method previously available.File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.