Arboricity and Subgraph Listing Algorithms

By Norishige Chiba, Takao Nishizeki. 1985

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Weisfeiler and Lehman Go Cellular: CW Networks (2021, background): “In the case of planar graphs, Chiba and Nishizeki [16] show linear time complexity to list triangles and quadratic complexity for 4-rings.”
Wedge sampling for computing clustering coefficients and triangle counts on large graphs † (2013, methodology): “3 Related Work There has been significant work on enumeration of all triangles [8, 25, 20, 5, 9].”
Inferring gene ontologies from pairwise similarity data (2014, methodology): “We use an algorithm proposed by Chiba and Nishizeki (1985) to compute all maximal cliques in time O ( m (cid”
Querying k-truss community in large and dynamic graphs (2014, unknown): “According to [6], O( ∑ (u,v)∈E min{d(u), d(v)}) ⊆O(ρm) where ρ is the arboricity of a graph G.”
Main-memory triangle computations for very large (sparse (power-law)) graphs (2008, background): “Triangle problemsmay be considered as classical, natural and fundamental algorithmic questions, and have been studied as such [24,14,2,3,33,34].”
Counting triangles and the curse of the last reducer (2011, background): “(Refer to [7] for further details and deﬁnitions.)”
EVEN-HOLE-FREE GRAPHS: A SURVEY (2010, methodology): “In [48] an O(nmk) algorithm for generating all maximal cliques of a graph is given, and in [5] this complexity is improved to O(m1.”
A survey of community search over big graphs (2019, background): “trong keyword cohesiveness. 10.4 Graph Pattern Matching (GPM) For simple graphs, the problem of GPM is NP-complete [44] and it has been studied extensively under dierent settings: (1) in main memory [182,38]. For example, Ullmann [182] proposed a backtracking algorithms. (2) in external memory, Chu ”
EmptyHeaded: A Relational Engine for Graph Processing (2015, methodology): “icitly orders the nodes. The choice of ˇ(v i) aects the internal skew of a sets the graph. Node ordering may impact the performance of a class of symmetrical queries like triangle without selections [15,28,51]. The key idea of this method is given an undirected graph, one creates a new directed grap”
Mind the gap (2006, background): “First, since subpatterns can be suffixes of each other, up to lsc vertices can arrive simultaneously in GD, which is the backbone of our algorithms.”
Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time (2010, methodology): “Another algorithm of Chiba and Nishizeki [10] lists cliques of order l in time O(lal−2m).”
New Algorithms for Enumerating All Maximal Cliques (2004, background): “Chiba and Nishizeki [7] reduced the time complexity to O(a(G)m), where a(G) is the arboricity of G with m/(n − 1) ≤ a(G) ≤ m 1/2 .”
Local Higher-Order Graph Clustering (2017, methodology): “For `-clique motifs, we use the method of Chiba and Nishizeki to compute the adjacency matrix W in O (`a`−2m) time, where a is the arboricity of the graph [7] and m is the number of edges in the graph.”
Listing All Maximal Cliques in Large Sparse Real-World Graphs (2011, background): “Algorithms for listing all maximal cliques in graphs of constant degeneracy in time O(n) were known [Chiba and Nishizeki 1985; Chrobak and Eppstein 1991], but had not been analyzed for their dependence on degeneracy.”