Extended dynamic subgraph statistics using h-index parameterized data structures

DOI10.1016/J.TCS.2011.11.034MaRDI QIDQ443712zbMATH OpenOpenAlexFDO

Authors Michael T. Goodrich, Darren Strash, Lowell Trott, David Eppstein

Publication date 13 August 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.0783

zbMATH Keywords

\(h\)-indexdynamic graph algorithmparameterized algorithmsubgraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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.

Recommendations

• Extended dynamic subgraph statistics using \(h\)-index parameterized data structures
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
• A dynamic data structure for counting subgraphs in sparse graphs
• Arboricity, \(h\)-index, and dynamic algorithms

Cites work

• An index to quantify an individual's scientific research output
• Arboricity and Subgraph Listing Algorithms
• Diameter and treewidth in minor-closed graph families
• Finding a Minimum Circuit in a Graph
• Finding and counting given length cycles
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Logit models and logistic regressions for social networks. I: An introduction to Markov graphs and \(p^*\)
• Markov Graphs
• Matrix multiplication via arithmetic progressions
• On efficient fixed-parameter algorithms for weighted vertex cover
• Statistical analysis of change in networks
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
• The Structure and Function of Complex Networks

Cited in

(7)

• A dynamic data structure for counting subgraphs in sparse graphs
• Extended dynamic subgraph statistics using \(h\)-index parameterized data structures
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics
• Quasipolynomiality of the Smallest Missing Induced Subgraph
• On linear algebraic algorithms for the subgraph matching problem and its variants
• Introducing weighted triad census through peeling algorithm. An application to football passing networks

This page was built for publication: Extended dynamic subgraph statistics using \(h\)-index parameterized data structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q443712)