{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T04:57:55Z","timestamp":1755838675379,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","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":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_40","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"544-557","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Efficient Algorithms for Listing k Disjoint st-Paths in Graphs"],"prefix":"10.1007","author":[{"given":"Roberto","family":"Grossi","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Marino","sequence":"additional","affiliation":[]},{"given":"Luca","family":"Versari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"40_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-642-34109-0_13","volume-title":"String Processing and Information Retrieval","author":"E Birmel\u00e9","year":"2012","unstructured":"Birmel\u00e9, E., Crescenzi, P., Ferreira, R., Grossi, R., Lacroix, V., Marino, A., Pisanti, N., Sacomoto, G., Sagot, M.-F.: Efficient bubble enumeration in directed graphs. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol. 7608, pp. 118\u2013129. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-34109-0_13"},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"Birmel\u00e9, E., Ferreira, R.A., Grossi, R., Marino, A., Pisanti, N., Rizzi, R., Sacomoto, G.: Optimal listing of cycles and st-paths in undirected graphs. In: Proceedings of the SODA, pp. 1884\u20131896 (2013)","DOI":"10.1137\/1.9781611973105.134"},{"issue":"2","key":"40_CR3","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0166-218X(97)00121-2","volume":"85","author":"T Eilam-Tzoreff","year":"1998","unstructured":"Eilam-Tzoreff, T.: The disjoint shortest paths problem. Discrete Appl. Math. 85(2), 113\u2013138 (1998)","journal-title":"Discrete Appl. Math."},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"1003","DOI":"10.1007\/978-1-4939-2864-4_733","volume-title":"Encyclopedia of Algorithms","author":"D Eppstein","year":"2016","unstructured":"Eppstein, D.: $$k$$-best enumeration. In: Kao, M.Y. (ed.) Encyclopedia of Algorithms, pp. 1003\u20131006. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-642-27848-8"},{"issue":"2","key":"40_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10(2), 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"40_CR6","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1145\/290179.290181","volume":"45","author":"AV Goldberg","year":"1998","unstructured":"Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. J. ACM (JACM) 45(5), 783\u2013797 (1998)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"40_CR7","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0204007","volume":"4","author":"DB Johnson","year":"1975","unstructured":"Johnson, D.B.: Finding all the elementary circuits of a directed graph. SIAM J. Comput. 4(1), 77\u201384 (1975)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"40_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"DB Johnson","year":"1977","unstructured":"Johnson, D.B.: Efficient algorithms for shortest paths in sparse networks. J. ACM 24(1), 1\u201313 (1977)","journal-title":"J. ACM"},{"issue":"1","key":"40_CR9","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5(1), 45\u201368 (1975)","journal-title":"Networks"},{"issue":"2","key":"40_CR10","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.: The disjoint paths problem in quadratic time. J. Comb. Theory Ser. B 102(2), 424\u2013435 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"40_CR11","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0166-218X(90)90024-7","volume":"26","author":"C-L Li","year":"1990","unstructured":"Li, C.-L., McCormick, S.T., Simchi-Levi, D.: The complexity of finding two disjoint paths with min-max objective function. Discrete Appl. Math. 26(1), 105\u2013115 (1990)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"40_CR12","doi-asserted-by":"publisher","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen kurventheorie. Fundam. Math. 10(1), 96\u2013115 (1927)","journal-title":"Fundam. Math."},{"issue":"3","key":"40_CR13","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":"40_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/978-3-319-19315-1_28","volume-title":"Combinatorial Algorithms","author":"R Rizzi","year":"2015","unstructured":"Rizzi, R., Sacomoto, G., Sagot, M.-F.: Efficiently listing bounded length st-paths. In: Jan, K., Miller, M., Froncek, D. (eds.) IWOCA 2014. LNCS, vol. 8986, pp. 318\u2013329. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19315-1_28"},{"key":"40_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-642-40453-5_9","volume-title":"Algorithms in Bioinformatics","author":"G Sacomoto","year":"2013","unstructured":"Sacomoto, G., Lacroix, V., Sagot, M.-F.: A polynomial delay algorithm for the enumeration of bubbles with length constraints in directed graphs and its application to the detection of alternative splicing in RNA-seq data. In: Darling, A., Stoye, J. (eds.) WABI 2013. LNCS, vol. 8126, pp. 99\u2013111. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40453-5_9"},{"key":"40_CR16","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial optimization: polyhedra and efficiency. Springer Science & Business Media, Heidelberg (2003)"},{"issue":"3","key":"40_CR17","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0202017","volume":"2","author":"R Tarjan","year":"1973","unstructured":"Tarjan, R.: Enumeration of the elementary circuits of a directed graph. SIAM J. Comput. 2(3), 211\u2013216 (1973)","journal-title":"SIAM J. Comput."},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"722","DOI":"10.1145\/362814.362819","volume":"13","author":"JC Tiernan","year":"1970","unstructured":"Tiernan, J.C.: An efficient search algorithm to find the elementary circuits of a graph. Commun. ACM 13, 722\u2013726 (1970)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:03:47Z","timestamp":1709827427000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}