{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,4]],"date-time":"2025-04-04T14:24:59Z","timestamp":1743776699692},"publisher-location":"New York, NY","reference-count":45,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781493928637"},{"type":"electronic","value":"9781493928644"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-1-4939-2864-4_728","type":"book-chapter","created":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T20:48:01Z","timestamp":1553114881000},"page":"640-645","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Enumeration of Paths, Cycles, and Spanning Trees"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,4,22]]},"reference":[{"key":"122_CR5128","unstructured":"Bezem G, Leeuwen Jv (1987) Enumeration in graphs. Technical Report RUU-CS-87-07, Utrecht University"},{"key":"122_CR5129","doi-asserted-by":"publisher","first-page":"1884","DOI":"10.1137\/1.9781611973105.134","volume-title":"Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms","author":"E Birmel\u00e9","year":"2013","unstructured":"Birmel\u00e9 E, Ferreira R, Grossi R, Marino A, Pisanti N, Rizzi R, Sacomoto G, Sagot MF (2013) Optimal listing of cycles and st-paths in undirected graphs. In: Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms, New Orleans. SIAM, pp\u00a01884\u20131896"},{"key":"122_CR5130","first-page":"250","volume-title":"IEEE conference on computational complexity, San Diego","author":"Y Chen","year":"2007","unstructured":"Chen Y, Flum J (2007) On parameterized path and chordless path problems. In: IEEE conference on computational complexity, San Diego, pp\u00a0250\u2013263"},{"key":"122_CR5131","doi-asserted-by":"publisher","first-page":"51","DOI":"10.4007\/annals.2006.164.51","volume":"164","author":"M Chudnovsky","year":"2006","unstructured":"Chudnovsky M, Robertson N, Seymour P, Thomas R (2006) The strong perfect graph theorem. Ann Math 164:51\u2013229","journal-title":"Ann Math"},{"key":"122_CR5132","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/BF01581196","volume":"55","author":"M Conforti","year":"1992","unstructured":"Conforti M, Rao MR (1992) Structural properties and decomposition of linear balanced matrices. Math Program 55:129\u2013168","journal-title":"Math Program"},{"key":"122_CR5133","volume-title":"Graph theory. Graduate texts in mathematics","author":"R Diestel","year":"2005","unstructured":"Diestel R (2005) Graph theory. Graduate texts in mathematics. Springer, Berlin\/New York"},{"key":"122_CR5134","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1090\/S0002-9947-1959-0109161-6","volume":"93","author":"R Duffin","year":"1959","unstructured":"Duffin R (1959) An analysis of the wang algebra of networks. Trans Am Math Soc 93:114\u2013131","journal-title":"Trans Am Math Soc"},{"key":"122_CR5135","unstructured":"Ferreira RA, Grossi R, Rizzi R, Sacomoto G, Sagot M (2014) Amortized \n                  \n                    \n                      \u00d5\n                      (\n                      |\n                      V\n                      |\n                      )\n                    \n                  \n                  $$\\tilde{O}(\\vert V \\vert )$$\n                -delay algorithm for listing chordless cycles in undirected graphs. In: Proceedings of European symposium on algorithms. LNCS, vol\u00a08737. Springer, Berlin\/Heidelberg, pp\u00a0418\u2013429"},{"key":"122_CR5136","doi-asserted-by":"publisher","first-page":"1304","DOI":"10.1002\/andp.19023141320","volume":"9","author":"W Feussner","year":"1902","unstructured":"Feussner W (1902) Uber stromverzweigung in netzformigen leitern. Ann Physik 9:1304\u20131329","journal-title":"Ann Physik"},{"key":"122_CR5137","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1002\/andp.19043201208","volume":"15","author":"W Feussner","year":"1904","unstructured":"Feussner W (1904) Zur berechnung der stromstarke in netzformigen leitern. Ann Physik 15:385\u2013394","journal-title":"Ann Physik"},{"issue":"3","key":"122_CR5138","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1137\/0207024","volume":"7","author":"HN Gabow","year":"1978","unstructured":"Gabow HN, Myers EW (1978) Finding all spanning trees of directed and undirected graphs. SIAM J Comput 7(3):280\u2013287","journal-title":"SIAM J Comput"},{"issue":"3","key":"122_CR5139","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1016\/j.tcs.2005.10.021","volume":"351","author":"R Haas","year":"2006","unstructured":"Haas R, Hoffmann M (2006) Chordless paths through three vertices. Theor Comput Sci 351(3):360\u2013371","journal-title":"Theor Comput Sci"},{"issue":"5","key":"122_CR5140","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0016-0032(61)90036-9","volume":"272","author":"S Hakimi","year":"1961","unstructured":"Hakimi S (1961) On trees of a graph and their generation. J Frankl Inst 272(5):347\u2013359","journal-title":"J Frankl Inst"},{"key":"122_CR5141","volume-title":"IEEE Communication Theory Workshop, Cancun","author":"TR Halford","year":"2004","unstructured":"Halford TR, Chugg KM (2004) Enumerating and counting cycles in bipartite graphs. In: IEEE Communication Theory Workshop, Cancun"},{"key":"122_CR5142","doi-asserted-by":"crossref","unstructured":"Horv\u00e1th T, G\u00e4rtner T, Wrobel S (2004) Cyclic pattern kernels for predictive graph mining. In: Proceedings of 10th ACM SIGKDD, Seattle, pp\u00a0158\u2013167","DOI":"10.1145\/1014052.1014072"},{"issue":"1","key":"122_CR5143","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"DB Johnson","year":"1975","unstructured":"Johnson DB (1975) Finding all the elementary circuits of a directed graph. SIAM J Comput 4(1):77\u201384","journal-title":"SIAM J Comput"},{"key":"122_CR5144","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1137\/S009753979225030X","volume":"24","author":"S Kapoor","year":"1995","unstructured":"Kapoor S, Ramesh H (1995) Algorithms for enumerating all spanning trees of undirected and weighted graphs. SIAM J Comput 24:247\u2013265","journal-title":"SIAM J Comput"},{"key":"122_CR5145","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/978-3-540-68891-4_4","volume-title":"IPCO","author":"K Kawarabayashi","year":"2008","unstructured":"Kawarabayashi K, Kobayashi Y (2008) The induced disjoint paths problem. In: Lodi A, Panconesi A, Rinaldi G (eds) IPCO. Lecture notes in computer science, vol\u00a05035. Springer, Berlin\/Heidelberg, pp\u00a047\u201361"},{"key":"122_CR5146","doi-asserted-by":"crossref","unstructured":"Khachiyan L, Boros E, Borys K, Elbassioni K, Gurvich V (2006) Generating all vertices of a polyhedron is hard. In: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithm, society for industrial and applied mathematics, Philadelphia, SODA \u201906, Miami, pp\u00a0758\u2013765","DOI":"10.1145\/1109557.1109640"},{"key":"122_CR5147","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1186\/1471-2105-7-56","volume":"7","author":"S Klamt","year":"2006","unstructured":"Klamt S et al (2006) A methodology for the structural and functional analysis of signaling and regulatory networks. BMC Bioinform 7:56","journal-title":"BMC Bioinform"},{"key":"122_CR5148","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1186\/1471-2105-10-181","volume":"10","author":"S Klamt","year":"2009","unstructured":"Klamt S, von Kamp A (2009) Computing paths and cycles in biological interaction graphs. BMC Bioinform 10:181","journal-title":"BMC Bioinform"},{"key":"122_CR5149","first-page":"57","volume-title":"A new way to enumerate cycles in graph","author":"H Liu","year":"2006","unstructured":"Liu H, Wang J (2006) A new way to enumerate cycles in graph. In: AICT and ICIW, Washington, DC, USA pp\u00a057\u201359"},{"issue":"1","key":"122_CR5150","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1137\/0205007","volume":"5","author":"P Mateti","year":"1976","unstructured":"Mateti P, Deo N (1976) On algorithms for enumerating all circuits of a graph. SIAM J Comput 5(1):90\u201399","journal-title":"SIAM J Comput"},{"issue":"1","key":"122_CR5151","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1109\/TCT.1965.1082385","volume":"12","author":"G Minty","year":"1965","unstructured":"Minty G (1965) A simple algorithm for listing all the trees of a graph. IEEE Trans Circuit Theory 12(1):120\u2013120","journal-title":"IEEE Trans Circuit Theory"},{"key":"122_CR5152","unstructured":"Moon J (1970) Counting labelled trees. Canadian mathematical monographs, vol\u00a01. Canadian Mathematical Congress, Montreal"},{"key":"122_CR5153","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1137\/0114051","volume":"14","author":"J Ponstein","year":"1966","unstructured":"Ponstein J (1966) Self-avoiding paths and the adjacency matrix of a graph. SIAM J Appl Math 14:600\u2013609","journal-title":"SIAM J Appl Math"},{"issue":"3","key":"122_CR5154","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"RC Read","year":"1975","unstructured":"Read RC, Tarjan RE (1975) Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3):237\u2013252","journal-title":"Networks"},{"key":"122_CR5155","volume-title":"Combinatorial generation","author":"F Ruskey","year":"2003","unstructured":"Ruskey F (2003) Combinatorial generation. Preliminary working draft University of Victoria, Victoria"},{"key":"122_CR5156","first-page":"498","volume-title":"Intelligent and advanced systems, Kuala Lumpur","author":"K Sankar","year":"2007","unstructured":"Sankar K, Sarad A (2007) A time and memory efficient way to enumerate cycles in a graph. In: Intelligent and advanced systems, Kuala Lumpur pp\u00a0498\u2013500"},{"key":"122_CR5157","doi-asserted-by":"publisher","first-page":"1828","DOI":"10.1016\/j.camwa.2011.06.026","volume":"62","author":"R Schott","year":"2011","unstructured":"Schott R, Staples GS (2011) Complexity of counting cycles using Zeons. Comput Math Appl 62:1828\u20131837","journal-title":"Comput Math Appl"},{"issue":"2","key":"122_CR5158","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0095-8956(74)90063-X","volume":"16","author":"D Seinsche","year":"1974","unstructured":"Seinsche D (1974) On a property of the class of n-colorable graphs. J Comb Theory, Ser B 16(2):191\u2013193","journal-title":"J Comb Theory, Ser B"},{"key":"122_CR5159","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1137\/S0097539794270881","volume":"26","author":"A Shioura","year":"1994","unstructured":"Shioura A, Tamura A, Uno T (1994) An optimal algorithm for scanning all spanning trees of undirected graphs. SIAM J Comput 26:678\u2013692","journal-title":"SIAM J Comput"},{"key":"122_CR5160","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1021\/c160016a007","volume":"5","author":"E Sussenguth","year":"1965","unstructured":"Sussenguth E (1965) A graph-theoretical algorithm for matching chemical structures. J Chem Doc 5:36\u201343","journal-title":"J Chem Doc"},{"issue":"4","key":"122_CR5161","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1137\/0210062","volume":"10","author":"MM Syslo","year":"1981","unstructured":"Syslo MM (1981) An efficient cycle vector space algorithm for listing all cycles of a planar graph. SIAM J Comput 10(4):797\u2013808","journal-title":"SIAM J Comput"},{"key":"122_CR5162","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/BF01931370","volume":"16","author":"JL Szwarcfiter","year":"1976","unstructured":"Szwarcfiter JL, Lauer PE (1976) A search strategy for the elementary cycles of a directed graph. BIT Numer Math 16:192\u2013204","journal-title":"BIT Numer Math"},{"issue":"3","key":"122_CR5163","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0202017","volume":"2","author":"RE Tarjan","year":"1973","unstructured":"Tarjan RE (1973) Enumeration of the elementary circuits of a directed graph. SIAM J Comput 2(3):211\u2013216","journal-title":"SIAM J Comput"},{"key":"122_CR5164","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1145\/362814.362819","volume":"13","author":"JC Tiernan","year":"1970","unstructured":"Tiernan JC (1970) An efficient search algorithm to find the elementary circuits of a graph. Commun ACM 13:722\u2013726","journal-title":"Commun ACM"},{"key":"122_CR5165","first-page":"287","volume-title":"New approach for speeding up enumeration algorithms. Algorithms and computation","author":"T Uno","year":"1998","unstructured":"Uno T (1998) New approach for speeding up enumeration algorithms. Algorithms and computation. Springer, Berlin\/Heidelberg, pp\u00a0287\u2013296"},{"key":"122_CR5166","first-page":"349","volume-title":"A new approach for speeding up enumeration algorithms and its application for matroid bases","author":"T Uno","year":"1999","unstructured":"Uno T (1999) A new approach for speeding up enumeration algorithms and its application for matroid bases. In: COCOON, Tokyo, pp\u00a0349\u2013359"},{"key":"122_CR5167","unstructured":"Uno T (2003) An output linear time algorithm for enumerating chordless cycles. In: 92nd SIGAL of information processing society Japan, Tokyo pp\u00a047\u201353, (in Japanese)"},{"key":"122_CR5168","unstructured":"Uno T (2003) Two general methods to reduce delay and change of enumeration algorithms. National Institute of Informatics, Technical Report NII-2003-004E, Tokyo, Apr. 2003"},{"key":"122_CR5169","first-page":"19","volume":"2","author":"K Wang","year":"1934","unstructured":"Wang K (1934) On a new method for the analysis of electrical networks. Nat Res Inst for Eng Academia Sinica Memoir (2):19","journal-title":"Nat Res Inst for Eng Academia Sinica Memoir"},{"key":"122_CR5170","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1145\/321328.321331","volume":"13","author":"JT Welch Jr","year":"1966","unstructured":"Welch JT Jr (1966) A mechanical analysis of the cyclic structure of undirected linear graphs. J ACM 13:205\u2013210","journal-title":"J ACM"},{"key":"122_CR5171","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.jda.2007.01.005","volume":"6","author":"M Wild","year":"2008","unstructured":"Wild M (2008) Generating all cycles, chordless cycles, and hamiltonian cycles with the principle of exclusion. J Discret Algorithms 6:93\u2013102","journal-title":"J Discret Algorithms"},{"key":"122_CR5172","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1109\/TCT.1967.1082662","volume":"14","author":"S Yau","year":"1967","unstructured":"Yau S (1967) Generation of all hamiltonian circuits, paths, and centers of a graph, and related problems. IEEE Trans Circuit Theory 14:79\u201381","journal-title":"IEEE Trans Circuit Theory"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4939-2864-4_728","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,20]],"date-time":"2019-03-20T21:23:34Z","timestamp":1553117014000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4939-2864-4_728"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9781493928637","9781493928644"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_728","relation":{},"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"22 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}