Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics

Details Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics

2010-09-03

arxiv.org/abs/1009.0783v1

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284463