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.
@cite_31: In this paper we introduce a new simple strategy into edge-searching of a graph, which is useful to the various subgraph listing problems. Applying the strategy, we obtain the following four algorithms. The first one lists all the triangles in a graph G in @math time, where m is the number of edges of G and @math the arboricity of G. The second finds all the quadrangles in @math time. Since @math is at most three for a planar graph G, both run in linear time for a planar graph. The third lists all the complete subgraphs @math of order l in @math time. The fourth lists all the cliques in @math time per clique. All the algorithms require linear space. We also establish an upper bound on @math for a graph @math , where n is the number of vertices in G.
@cite_18: We give two algorithms for listing all simplicial vertices of a graph. The first of these algorithms takes O(nα) time, where n is the number of vertices in the graph and O(nα) is the time needed to perform a fast matrix multiplication. The second algorithm can be implemented to run in (O(e^ 2 + 1 ) = O(e^ 1.41 ) ), where e is the number of edges in the graph.
@cite_4: 
@cite_21: We provide simple, faster algorithms for the detection of cliques and dominating sets of fixed order. Our algorithms are based on reductions to rectangular matrix multiplication. We also describe an improved algorithm for diamonds detection.
@cite_1: It is known that any planar graph with diameter D has treewidth O(D) , and this fact has been used as the basis for several planar graph algorithms. We investigate the extent to which similar relations hold in other graph families. We show that treewidth is bounded by a function of the diameter in a minor-closed family, if and only if some apex graph does not belong to the family. In particular, the O(D) bound above can be extended to bounded-genus graphs. As a consequence, we extend several approximation algorithms and exact subgraph isomorphism algorithms from planar graphs to other graph families.
@cite_3: We present a new method for accelerating matrix multiplication asymptotically. Thiswork builds on recent ideas of Volker Strassen, by using a basic trilinear form which is not a matrix product. We make novel use of the Salem-Spencer Theorem, which gives a fairly dense set of integers with no three-term arithmetic progression. Our resulting matrix exponent is 2.376.
@cite_24: 
@cite_23: 
@cite_15: Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum. To find an almost minimum circuit an @math algorithm is presented. A direct algorithm for finding a minimum circuit has an @math behavior. It is refined to yield an @math average time algorithm. An alternative method is to reduce the problem of finding a minimum circuit to that of finding a triangle in an auxiliary graph. Three methods for finding a triangle in a graph are given. The first has an @math worst case bound ( @math for planar graphs); the second takes @math time on the average; the third has an @math worst case behavior. For digraphs, results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with @math average behavior.
@cite_13: We present a matrix multiplication based algorithm for counting the number of (induced) occurrences of a fixed r-uniform hypergraph in a larger hypergraph. In many cases, the running time is better than that of the naive algorithm. We also present several useful applications of the algorithm, such as determining the dominant color among monochromatic simplices in a red-blue edge-colored hypergraph, approximating the number of independent simplices in a random hypergraph, and counting induced occurrences of a given 3-uniform k-vertex hypergraph in a larger k-clique free hypergraph.
@cite_20: For a pattern graph H on k nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of H in a given large graph G on n nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include: The number of copies of an H with an independent set of size s can be computed exactly in O*(2s nk-s+3) time. A minimum weight copy of such an H (with arbitrary real weights on nodes and edges) can be found in O(4s+o(s) nk-s+3) time. (The O* notation omits (k) factors.) These algorithms rely on fast algorithms for computing the permanent of a k x n matrix, over rings and semirings. The number of copies of any H having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in O(nω k 3 + n2k 3+o(1)) time, where ω 0, unless the 3SUM problem on N numbers can be solved in O(N2 - e) time. This suggests that the edge-weighted problem is much harder than its node-weighted version.
Although subgraph isomorphism is known to be NP-complete, it is solvable in polynomial time for small subgraphs. For example, all triangles and four-cycles can be found in an @math -vertex graph with @math edges in @math time @cite_15 @cite_31 . All cycles up to length seven can be counted (but not listed) in @math time @cite_4 , where @math is the exponent for the asymptotically fastest known matrix multiplication algorithm @cite_3 . In addition, fast matrix multiplication has also been used for other problems of finding and counting small cliques in graphs and hypergraphs @cite_21 @cite_18 @cite_24 @cite_20 @cite_13 . Also, in planar graphs, the number of copies of any fixed subgraph may be found in linear time @cite_23 @cite_1 . These previous approaches run too slowly for the iterative nature of ERGM Markov Chain Monte Carlo simulations, however.