Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Extended Dynamic Subgraph Statistics Using h-Index Parameterized Data Structures
verfasst von : David Eppstein, Michael T. Goodrich, Darren Strash, Lowell Trott
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present techniques for maintaining subgraph frequencies in a dynamic graph, using data structures that are parameterized in terms of
h
, the
h-index
of the graph. Our methods extend previous results of Eppstein and Spiro for maintaining statistics for undirected subgraphs of size three to directed subgraphs and to subgraphs of size four. For the directed case, we provide a data structure to maintain counts for all 3-vertex induced subgraphs in
O
(
h
) amortized time per update. For the undirected case, we maintain the counts of size-four subgraphs in
O
(
h
2
) amortized time per update. These extensions enable a number of new applications in Bioinformatics and Social Networking research.