Enumerating graphlets with amortized time complexity independent of graph size

DOI10.1007/S00453-025-01312-0MaRDI QIDQ6936585zbMATH OpenFDO

Authors Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Takeaki Uno, Kunihiro Wasa

Publication date 29 August 2025

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-025-01312-0

zbMATH Keywords

amortizationenumerationgraph algorithmsgraphletssubgraphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

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)\).

Cites work

• A compact DAG for storing and searching maximal common subsequences
• A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
• A general method to speed up fixed-parameter-tractable algorithms
• A note on finding the bridges of a graph
• Algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality
• An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
• An efficient algorithm for enumerating induced subgraphs with bounded degeneracy
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• CAGE: cache-aware graphlet enumeration
• Constant time enumeration by amortization
• Constant time enumeration of bounded-size subtrees in trees and its application
• Efficient enumeration of bipartite subgraphs in graphs
• Enumerating connected induced subgraphs: improved delay and experimental comparison
• Enumeration of subtrees of planar two-tree networks
• Motif discovery in networks: a survey
• Optimal listing of cycles and st-paths in undirected graphs
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Some properties of line digraphs
• Subtrees of graphs

This page was built for publication: Enumerating graphlets with amortized time complexity independent of graph size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6936585)