Enumerating graphlets with amortized time complexity independent of graph size (Q6936585)

Given a graph \(G\), graphlets of order \(k\) are its connected subgraphs induced by \(k\) vertices (called \(k\)-graphlets) or by \(k\) edges (called edge \(k\)-graphlets). In this paper, the authors provide an algorithm to list all graphlets of order \(k\) in a graph \(G\) with an amortized time complexity depending solely on the order \(k\). They show that it is possible to list \(k\)-graphlets in \(O(k^2)\) time per solution, and to list edge \(k\)-graphlets in \(O(k)\) time per solution. If the maximum degree \(\bigtriangleup(G) \) is bounded by a constant, then the amortized time for listing \(k\)-graphlets is reduced to \(O(k)\).