{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T19:11:42Z","timestamp":1757617902714,"version":"3.44.0"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T00:00:00Z","timestamp":1747094400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T00:00:00Z","timestamp":1747094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2022TS4Y3N","2022TS4Y3N","2022TS4Y3N"],"award-info":[{"award-number":["2022TS4Y3N","2022TS4Y3N","2022TS4Y3N"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ISTI - PISA"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Graphlets of order\u00a0<jats:italic>k<\/jats:italic> in a graph <jats:italic>G<\/jats:italic> are connected subgraphs induced by <jats:italic>k<\/jats:italic>\u00a0nodes (called <jats:italic>k<\/jats:italic>-graphlets) or by <jats:italic>k<\/jats:italic>\u00a0edges (called edge <jats:italic>k<\/jats:italic>-graphlets). They are among the interesting subgraphs in network analysis to get insights on both the local and global structure of a network. While several algorithms exist for discovering and enumerating graphlets, the amortized time complexity of such algorithms typically depends on the size of the graph <jats:italic>G<\/jats:italic>, or its maximum degree. In real networks, even the latter can be in the order of millions, whereas <jats:italic>k<\/jats:italic> is typically required to be a small value. In this paper we provide the first algorithm to list all graphlets of order\u00a0<jats:italic>k<\/jats:italic> in a graph <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$G=(V,E)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> with an amortized time complexity depending <jats:italic>solely<\/jats:italic> on the order <jats:italic>k<\/jats:italic>, contrarily to previous approaches where the cost depends <jats:italic>also<\/jats:italic> on the size of <jats:italic>G<\/jats:italic> or its maximum degree. Specifically, we show that it is possible to list <jats:italic>k<\/jats:italic>-graphlets in <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O(k^2)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> time per solution, and to list edge <jats:italic>k<\/jats:italic>-graphlets in <jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic>) time per solution. Furthermore we show that, if the input graph has bounded degree, then the amortized time for listing <jats:italic>k<\/jats:italic>-graphlets is reduced to <jats:italic>O<\/jats:italic>(<jats:italic>k<\/jats:italic>). Whenever <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$k = O(1)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, as it is often the case in practical settings, these algorithms are the first to achieve constant time per solution.<\/jats:p>","DOI":"10.1007\/s00453-025-01312-0","type":"journal-article","created":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T17:14:47Z","timestamp":1747156487000},"page":"1247-1273","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size"],"prefix":"10.1007","volume":"87","author":[{"given":"Alessio","family":"Conte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasuaki","family":"Kobayashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhiro","family":"Kurita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Davide","family":"Rucci","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunihiro","family":"Wasa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,13]]},"reference":[{"issue":"4","key":"1312_CR1","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1109\/TCBB.2006.55","volume":"3","author":"V Lacroix","year":"2006","unstructured":"Lacroix, V., Fernandes, C.G., Sagot, M.-F.: Motif search in graphs: application to metabolic networks. IEEE\/ACM Trans. Comput. Biol. Bioinform. 3(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"2","key":"1312_CR2","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1093\/bfgp\/eln015","volume":"7","author":"G Ciriello","year":"2008","unstructured":"Ciriello, G., Guerra, C.: A review on models and algorithms for motif discovery in protein\u2013protein interaction networks. Brief. Funct. Genom. 7(2), 147\u2013156 (2008). https:\/\/doi.org\/10.1093\/bfgp\/eln015","journal-title":"Brief. Funct. Genom."},{"key":"1312_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2020.100267","volume":"37","author":"S Yu","year":"2020","unstructured":"Yu, S., Feng, Y., Zhang, D., Bedru, H.D., Xu, B., Xia, F.: Motif discovery in networks: a survey. Comput. Sci. Rev. 37, 100267 (2020)","journal-title":"Comput. Sci. Rev."},{"issue":"3","key":"1312_CR4","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","volume":"486","author":"S Fortunato","year":"2010","unstructured":"Fortunato, S.: Community detection in graphs. Phys. Rep. 486(3), 75\u2013174 (2010). https:\/\/doi.org\/10.1016\/j.physrep.2009.11.002","journal-title":"Phys. Rep."},{"issue":"18","key":"1312_CR5","doi-asserted-by":"publisher","first-page":"3508","DOI":"10.1093\/bioinformatics\/bth436","volume":"20","author":"N Pr\u017eulj","year":"2004","unstructured":"Pr\u017eulj, N., Corneil, D.G., Jurisica, I.: Modeling interactome: Scale-free or geometric? Bioinformatics 20(18), 3508\u20133515 (2004). https:\/\/doi.org\/10.1093\/bioinformatics\/bth436","journal-title":"Bioinformatics"},{"key":"1312_CR6","unstructured":"Shervashidze, N., Vishwanathan, S., Petri, T., Mehlhorn, K., Borgwardt, K.: Efficient graphlet kernels for large graph comparison. In: Artificial Intelligence and Statistics, pp. 488\u2013495. PMLR (2009)"},{"issue":"1","key":"1312_CR7","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/s41109-019-0195-3","volume":"5","author":"NM Kriege","year":"2020","unstructured":"Kriege, N.M., Johansson, F.D., Morris, C.: A survey on graph kernels. Appl. Netw. Sci. 5(1), 6 (2020). https:\/\/doi.org\/10.1007\/s41109-019-0195-3","journal-title":"Appl. Netw. Sci."},{"issue":"1","key":"1312_CR8","doi-asserted-by":"publisher","first-page":"0261676","DOI":"10.1371\/journal.pone.0261676","volume":"17","author":"SF Windels","year":"2022","unstructured":"Windels, S.F., Malod-Dognin, N., Pr\u017eulj, N.: Graphlet eigencentralities capture novel central roles of genes in pathways. PLoS ONE 17(1), 0261676 (2022)","journal-title":"PLoS ONE"},{"key":"1312_CR9","doi-asserted-by":"crossref","unstructured":"Apar\u00edcio, D., Ribeiro, P., Silva, F., Silva, J.: Finding dominant nodes using graphlets. In: Complex Networks, pp. 77\u201389. Springer (2019)","DOI":"10.1007\/978-3-030-36687-2_7"},{"key":"1312_CR10","unstructured":"Klymko, C., Gleich, D., Kolda, T.G.: Using triangles to improve community detection in directed networks (2014). arXiv preprint arXiv:1404.5874"},{"key":"1312_CR11","doi-asserted-by":"publisher","unstructured":"Prat-P\u00e9rez, A., Dominguez-Sal, D., Brunat, J.M., Larriba-Pey, J.-L.: Shaping communities out of triangles. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management. CIKM \u201912, pp. 1677\u20131681. Association for Computing Machinery, New York, NY, USA (2012). https:\/\/doi.org\/10.1145\/2396761.2398496","DOI":"10.1145\/2396761.2398496"},{"key":"1312_CR12","doi-asserted-by":"publisher","unstructured":"Friggeri, A., Chelius, G., Fleury, E.: Triangles to capture social cohesion. In: 2011 IEEE Third International Conference on Privacy, Security, Risk and Trust and 2011 IEEE Third International Conference on Social Computing, pp. 258\u2013265 (2011). https:\/\/doi.org\/10.1109\/PASSAT\/SocialCom.2011.169","DOI":"10.1109\/PASSAT\/SocialCom.2011.169"},{"key":"1312_CR13","doi-asserted-by":"publisher","unstructured":"Jabbour, S., Mhadbhi, N., Raddaoui, B., Sais, L.: Triangle-driven community detection in large graphs using propositional satisfiability. In: 2018 IEEE 32nd International Conference on Advanced Information Networking and Applications (AINA), pp. 437\u2013444 (2018). https:\/\/doi.org\/10.1109\/AINA.2018.00072","DOI":"10.1109\/AINA.2018.00072"},{"issue":"4","key":"1312_CR14","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1002\/jgt.22359","volume":"89","author":"AJ Chin","year":"2018","unstructured":"Chin, A.J., Gordon, G., MacPhee, K.J., Vincent, C.: Subtrees of graphs. J. Graph Theory 89(4), 413\u2013438 (2018). https:\/\/doi.org\/10.1002\/jgt.22359","journal-title":"J. Graph Theory"},{"key":"1312_CR15","doi-asserted-by":"publisher","unstructured":"Zhang, S., Hu, M., Yang, J.: Treepi: A novel graph indexing method. In: 2007 IEEE 23rd International Conference on Data Engineering, pp. 966\u2013975 (2007). https:\/\/doi.org\/10.1109\/ICDE.2007.368955","DOI":"10.1109\/ICDE.2007.368955"},{"issue":"15","key":"1312_CR16","doi-asserted-by":"publisher","first-page":"2038","DOI":"10.1016\/j.patrec.2012.03.020","volume":"33","author":"B Ga\u00fcz\u00e8re","year":"2012","unstructured":"Ga\u00fcz\u00e8re, B., Brun, L., Villemin, D.: Two new graphs kernels in chemoinformatics. Pattern Recogn. Lett. 33(15), 2038\u20132047 (2012). https:\/\/doi.org\/10.1016\/j.patrec.2012.03.020","journal-title":"Pattern Recogn. Lett."},{"key":"1312_CR17","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2022.127404","volume":"434","author":"D Sun","year":"2022","unstructured":"Sun, D., Li, L., Liu, K., Wang, H., Yang, Y.: Enumeration of subtrees of planar two-tree networks. Appl. Math. Comput. 434, 127404 (2022). https:\/\/doi.org\/10.1016\/j.amc.2022.127404","journal-title":"Appl. Math. Comput."},{"key":"1312_CR18","unstructured":"Wasa, K.: Enumeration of enumeration algorithms. CoRR (2016). arXiv:1605.05102"},{"key":"1312_CR19","doi-asserted-by":"publisher","unstructured":"Uno, T.: Constant time enumeration by amortization. In: Algorithms and Data Structures\u201414th International Symposium, WADS 2015, Victoria, BC, Canada, August 5\u20137, 2015. Proceedings, pp. 593\u2013605 (2015). https:\/\/doi.org\/10.1007\/978-3-319-21840-3_49","DOI":"10.1007\/978-3-319-21840-3_49"},{"issue":"3\u20134","key":"1312_CR20","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(00)00004-1","volume":"73","author":"R Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: A general method to speed up fixed-parameter-tractable algorithms. Inf. Process. Lett. 73(3\u20134), 125\u2013129 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1312_CR21","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.tcs.2005.10.004","volume":"351","author":"P Damaschke","year":"2006","unstructured":"Damaschke, P.: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351(3), 337\u2013350 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2005.10.004","journal-title":"Theor. Comput. Sci."},{"key":"1312_CR22","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/11557067_14","volume-title":"Algorithms in Bioinformatics","author":"S Wernicke","year":"2005","unstructured":"Wernicke, S.: A faster algorithm for detecting network motifs. In: Casadio, R., Myers, G. (eds.) Algorithms in Bioinformatics, pp. 165\u2013177. Springer, Berlin, Heidelberg (2005)"},{"issue":"9","key":"1312_CR23","doi-asserted-by":"publisher","first-page":"1152","DOI":"10.1093\/bioinformatics\/btl038","volume":"22","author":"S Wernicke","year":"2006","unstructured":"Wernicke, S., Rasche, F.: FANMOD: a tool for fast network motif detection. Bioinformatics 22(9), 1152\u20131153 (2006). https:\/\/doi.org\/10.1093\/bioinformatics\/btl038","journal-title":"Bioinformatics"},{"key":"1312_CR24","doi-asserted-by":"publisher","unstructured":"Pinar, A., Seshadhri, C., Vishal, V.: Escape: efficiently counting all 5-vertex subgraphs. In: Proceedings of the 26th International Conference on World Wide Web. WWW \u201917, pp. 1431\u20131440. International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE (2017). https:\/\/doi.org\/10.1145\/3038912.3052597","DOI":"10.1145\/3038912.3052597"},{"key":"1312_CR25","doi-asserted-by":"publisher","unstructured":"Paredes, P., Ribeiro, P.: Towards a faster network-centric subgraph census. In: 2013 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013), pp. 264\u2013271 (2013). https:\/\/doi.org\/10.1145\/2492517.2492535","DOI":"10.1145\/2492517.2492535"},{"issue":"1","key":"1312_CR26","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1186\/1471-2105-10-318","volume":"10","author":"ZRM Kashani","year":"2009","unstructured":"Kashani, Z.R.M., Ahrabian, H., Elahi, E., Nowzari-Dalini, A., Ansari, E.S., Asadi, S., Mohammadi, S., Schreiber, F., Masoudi-Nejad, A.: Kavosh: a new algorithm for finding network motifs. BMC Bioinform. 10(1), 318 (2009). https:\/\/doi.org\/10.1186\/1471-2105-10-318","journal-title":"BMC Bioinform."},{"issue":"8","key":"1312_CR27","doi-asserted-by":"publisher","first-page":"1372","DOI":"10.1093\/bioinformatics\/btx758","volume":"34","author":"I Melckenbeeck","year":"2017","unstructured":"Melckenbeeck, I., Audenaert, P., Colle, D., Pickavet, M.: Efficiently counting all orbits of graphlets of any order in a graph using autogenerated equations. Bioinformatics 34(8), 1372\u20131380 (2017). https:\/\/doi.org\/10.1093\/bioinformatics\/btx758","journal-title":"Bioinformatics"},{"issue":"2","key":"1312_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3433652","volume":"54","author":"P Ribeiro","year":"2021","unstructured":"Ribeiro, P., Paredes, P., Silva, M.E.P., Aparicio, D., Silva, F.: A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Comput. Surv. 54(2), 1\u201336 (2021). https:\/\/doi.org\/10.1145\/3433652","journal-title":"ACM Comput. Surv."},{"key":"1312_CR29","doi-asserted-by":"publisher","unstructured":"Ahmed, N.K., Neville, J., Rossi, R.A., Duffield, N.: Efficient graphlet counting for large networks. In: 2015 IEEE International Conference on Data Mining, pp. 1\u201310 (2015). https:\/\/doi.org\/10.1109\/ICDM.2015.141","DOI":"10.1109\/ICDM.2015.141"},{"key":"1312_CR30","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.04.036","author":"C Komusiewicz","year":"2020","unstructured":"Komusiewicz, C., Sommer, F.: Enumerating connected induced subgraphs: improved delay and experimental comparison. Discrete Appl. Math. (2020). https:\/\/doi.org\/10.1016\/j.dam.2020.04.036","journal-title":"Discrete Appl. Math."},{"key":"1312_CR31","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-031-43980-3_11","volume-title":"String Processing and Information Retrieval","author":"A Conte","year":"2023","unstructured":"Conte, A., Grossi, R., Rucci, D.: Cage: cache-aware graphlet enumeration. In: Nardini, F.M., Pisanti, N., Venturini, R. (eds.) String Processing and Information Retrieval, pp. 129\u2013142. Springer, Cham (2023)"},{"key":"1312_CR32","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2023.106425","volume":"183","author":"S Wang","year":"2024","unstructured":"Wang, S., Xiao, C., Casseau, E.: Algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality. Inf. Process. Lett. 183, 106425 (2024). https:\/\/doi.org\/10.1016\/j.ipl.2023.106425","journal-title":"Inf. Process. Lett."},{"issue":"S1","key":"1312_CR33","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1017\/nws.2020.35","volume":"9","author":"X Liu","year":"2021","unstructured":"Liu, X., Chen, Y.-Z.J., Lui, J.C., Avrachenkov, K.: Learning to count: a deep learning framework for graphlet count estimation. Netw. Sci. 9(S1), 23\u201360 (2021)","journal-title":"Netw. Sci."},{"issue":"3","key":"1312_CR34","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"RC Read","year":"1975","unstructured":"Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3), 237\u2013252 (1975)","journal-title":"Networks"},{"key":"1312_CR35","doi-asserted-by":"crossref","unstructured":"Birmel\u00e9, E., Ferreira, R., Grossi, R., Marino, A., Pisanti, N., Rizzi, R., Sacomoto, G.: Optimal listing of cycles and ST-paths in undirected graphs. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201913, pp. 1884\u20131896. Society for Industrial and Applied Mathematics, USA (2013)","DOI":"10.1137\/1.9781611973105.134"},{"issue":"4","key":"1312_CR36","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1145\/322217.322220","volume":"27","author":"S Tsukiyama","year":"1980","unstructured":"Tsukiyama, S., Shirakawa, I., Ozaki, H., Ariyoshi, H.: An algorithm to enumerate all cutsets of a graph in linear time per cutset. J. ACM 27(4), 619\u2013632 (1980)","journal-title":"J. ACM"},{"key":"1312_CR37","doi-asserted-by":"crossref","unstructured":"Wasa, K., Uno, T.: Efficient enumeration of bipartite subgraphs in graphs. In: Computing and Combinatorics\u201424th International Conference, COCOON 2018, Qing Dao, China, July 2\u20134, 2018, Proceedings. Lecture Notes in Computer Science, vol. 10976, pp. 454\u2013466. Springer, Cham, Switzerland (2018)","DOI":"10.1007\/978-3-319-94776-1_38"},{"issue":"9","key":"1312_CR38","doi-asserted-by":"publisher","first-page":"1383","DOI":"10.1587\/transfun.E101.A.1383","volume":"E101\u2013A","author":"K Kurita","year":"2018","unstructured":"Kurita, K., Wasa, K., Uno, T., Arimura, H.: Efficient enumeration of induced matchings in a graph without cycles with length four. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E101\u2013A(9), 1383\u20131391 (2018)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"1312_CR39","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-030-04651-4_3","volume-title":"Combinatorial Optimization and Applications","author":"K Wasa","year":"2018","unstructured":"Wasa, K., Uno, T.: An efficient algorithm for enumerating induced subgraphs with bounded degeneracy. In: Kim, D., Uma, R.N., Zelikovsky, A. (eds.) Combinatorial Optimization and Applications, pp. 35\u201345. Springer, Cham (2018)"},{"key":"1312_CR40","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/J.TCS.2021.05.008","volume":"874","author":"K Kurita","year":"2021","unstructured":"Kurita, K., Wasa, K., Uno, T., Arimura, H.: A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number. Theor. Comput. Sci. 874, 32\u201341 (2021). https:\/\/doi.org\/10.1016\/J.TCS.2021.05.008","journal-title":"Theor. Comput. Sci."},{"key":"1312_CR41","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/978-3-642-32241-9_30","volume-title":"Computing and Combinatorics","author":"K Wasa","year":"2012","unstructured":"Wasa, K., Kaneta, Y., Uno, T., Arimura, H.: Constant time enumeration of bounded-size subtrees in trees and its application. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds.) Computing and Combinatorics, pp. 347\u2013359. Springer, Berlin, Heidelberg (2012)"},{"key":"1312_CR42","unstructured":"Uno, T.: Two general methods to reduce delay and change of enumeration algorithms (2003)"},{"issue":"6","key":"1312_CR43","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0020-0190(74)90003-9","volume":"2","author":"RE Tarjan","year":"1974","unstructured":"Tarjan, R.E.: A note on finding the bridges of a graph. Inf. Process. Lett. 2(6), 160\u2013161 (1974). https:\/\/doi.org\/10.1016\/0020-0190(74)90003-9","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"1312_CR44","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372\u2013378 (1973). https:\/\/doi.org\/10.1145\/362248.362272","journal-title":"Commun. ACM"},{"issue":"2","key":"1312_CR45","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF02854581","volume":"9","author":"F Harary","year":"1960","unstructured":"Harary, F., Norman, R.Z.: Some properties of line digraphs. Rend. Circ. Mat. Palermo 9(2), 161\u2013168 (1960). https:\/\/doi.org\/10.1007\/BF02854581","journal-title":"Rend. Circ. Mat. Palermo"},{"key":"1312_CR46","doi-asserted-by":"publisher","unstructured":"Conte, A., Grossi, R., Punzi, G., Uno, T.: A compact DAG for storing and searching maximal common subsequences. In: Iwata, S., Kakimura, N. (eds.) 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 283, pp. 21\u201312115. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2023.21","DOI":"10.4230\/LIPIcs.ISAAC.2023.21"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01312-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01312-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01312-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T14:52:55Z","timestamp":1757170375000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01312-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,13]]},"references-count":46,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["1312"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01312-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2025,5,13]]},"assertion":[{"value":"25 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}