The number of triangles in a graph is an important metric for understanding the graph. It is also directly related to the clustering coefficient of a graph, which is one of the most important indicator for social networks. Counting the number of triangles is computationally expensive for very large graphs. Hence, estimation is necessary for large graphs, particularly for graphs that are hidden behind searchable interfaces where the graphs in their entirety are not available. For instance, user networks in Twitter and Facebook are not available for third parties to explore their properties directly. This paper proposes a new method to estimate the number of triangles based on random edge sampling. It improves the traditional random edge sampling by probing the edges that have a higher probability of forming triangles. The method outperforms the traditional method consistently, and can be better by orders of magnitude when the graph is very large. The result is demonstrated on 20 graphs, including the largest graphs we can find. More importantly, we proved the improvement ratio, and verified our result on all the datasets. The analytical results are achieved by simplifying the variances of the estimators based on the assumption that the graph is very large. We believe that such big data assumption can lead to interesting results not only in triangle estimation, but also in other sampling problems.

Two parallel algorithms for finding the lowest common ancestors of a set of vertex pairs Q (the query set) in a directed tree are presented. With all the overheads taken into account, these algorithms take O((n + QI) P log2 n) and O(n2/p + log2n) time, respectively, with p(> 0) processors (n is the size of the tree). These results are better than the best known result in that the first achieves the O(log2 n) time bound with only n + |Q| processors while the second reduces the number of processors used by a factor of log2 n which is optimal for large query sets when 0 < p ≤ n2/log2 n. The computer model we use here is the PRAM which is an SIMD model allowing read but not write conflicts. Our results also imply the following improvements: the processor bound for finding a set of fundamental cycles in an undirected graph is improved by a factor of log2 n and the result is optimal for dense graphs; the implementations of some other sequential and parallel algorithms are also simplified.

In this paper, we present efficient parallel algorithms for the following graph problems: finding the lowest common ancestors for vertex pairs of a directed tree; finding all fundamental cycles, a directed spanning forest, all bridges, all bridge-connected components, all separation vertices, all biconnected components, and testing the biconnectivity of an undirected graph. All these algorithms achieve the $O(\lg ^2 n)$ time bound, with the first two algorithms using $n\lceil n /\lg n\rceil $ processors and the remaining algorithms using $n\lceil n/\lg ^2 n \rceil $ processors. In all cases, our algorithms are better than the previously known algorithms and in most cases reduce the number of processors used by a factor of $n\lg n$. Moreover, our algorithms are optimal with respect to the time-processor product for dense graphs, with the exception of the first two algorithms. The machine model we use is the PRAM which is a SIMD model allowing simultaneous reads but not simultaneous writes to the same memory location.

Abstract The CDC Pascal 6000–3.4 compiler allows external procedures to be designed and compiled separately. Such a mechanism strongly enhances the extensibility of the language. However, the external procedures are restricted to having ‘fixed’ parameter list only and is therefore unsuitable for designing I/O routines. This paper describes a cheap way to release the restriction thereby extending the power of the external procedure mechanism significantly. The method is to include a new compiler option, called the Z option, to the existing Pascal compiler. The Z option allows a user to breach the strong binding between format and actual parameters while not diminishing program reliability. The main advantage is that the I/O system can now be isolated from the compiler. I/O features can be added and removed easily as with other library routines.