Extended dynamic subgraph statistics using <i>h</i>-index parameterized data structures

作     者：Eppstein, David Goodrich, Michael T. Strash, Darren Trott, Lowell 

作者机构：Univ Calif Irvine Dept Comp Sci Irvine CA 92717 USA 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 

年 卷 期：2012年第447卷

页      面：44-52页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Direct For Computer & Info Scie & Enginr Division of Computing and Communication Foundations Funding Source: National Science Foundation 

主　　题：Parameterized algorithm Subgraph h-index Dynamic graph algorithm 

摘      要：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. (c) 2011 Elsevier B.V. All rights reserved.