{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:43:04Z","timestamp":1777596184372,"version":"3.51.4"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,12,12]],"date-time":"2019-12-12T00:00:00Z","timestamp":1576108800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,12]],"date-time":"2019-12-12T00:00:00Z","timestamp":1576108800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010)"],"award-info":[{"award-number":["DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010)"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["304576\/2017-4 and 304478\/2018-0, CNPq Universal Project 401519\/2016-3"],"award-info":[{"award-number":["304576\/2017-4 and 304478\/2018-0, CNPq Universal Project 401519\/2016-3"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005283","name":"Funda\u00e7\u00e3o Cearense de Apoio ao Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["FUNCAP-PRONEM PNE-0112-00061.01.00\/16"],"award-info":[{"award-number":["FUNCAP-PRONEM PNE-0112-00061.01.00\/16"]}],"id":[{"id":"10.13039\/501100005283","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["CAPES-PRINT"],"award-info":[{"award-number":["CAPES-PRINT"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00453-019-00659-5","type":"journal-article","created":{"date-parts":[[2019,12,12]],"date-time":"2019-12-12T15:07:51Z","timestamp":1576163271000},"page":"1616-1639","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths"],"prefix":"10.1007","volume":"82","author":[{"given":"J\u00falio","family":"Ara\u00fajo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Victor A.","family":"Campos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ana Karolinna","family":"Maia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8981-9287","authenticated-orcid":false,"given":"Ignasi","family":"Sau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ana","family":"Silva","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,12]]},"reference":[{"issue":"4","key":"659_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"659_CR2","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J Bang-Jensen","year":"2008","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, Berlin (2008)","edition":"2"},{"key":"659_CR3","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/j.tcs.2014.10.004","volume":"562","author":"J Bang-Jensen","year":"2015","unstructured":"Bang-Jensen, J., Havet, F., Maia, A.K.: Finding a subdivision of a digraph. Theor. Comput. Sci. 562, 283\u2013303 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"659_CR4","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1002\/jgt.3190070413","volume":"7","author":"A Benhocine","year":"1983","unstructured":"Benhocine, A., Wojda, A.P.: On the existence of specified cycles in a tournament. J. Graph Theory 7(4), 469\u2013473 (1983)","journal-title":"J. Graph Theory"},{"key":"659_CR5","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Khanna, S.: Approximating longest directed paths and cycles. In: Proceeding of the 31st International Colloquium on Automata, Languages and Programming (ICALP). volume 3142 of LNCS. pp. 222\u2013233 (2004)","DOI":"10.1007\/978-3-540-27836-8_21"},{"issue":"1","key":"659_CR6","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"659_CR7","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1002\/jgt.10126","volume":"44","author":"RC Brewster","year":"2003","unstructured":"Brewster, R.C., Hell, P., Pantel, S.H., Rizzi, R., Yeo, A.: Packing paths in digraphs. J. Graph Theory 44(2), 81\u201394 (2003)","journal-title":"J. Graph Theory"},{"key":"659_CR8","doi-asserted-by":"crossref","unstructured":"Cai,L., Ye, J.: Finding two edge-disjoint paths with length constraints. In: Proceeding of the 42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG). volume 9941 of LNCS. pp. 62\u201373 (2016)","DOI":"10.1007\/978-3-662-53536-3_6"},{"issue":"4","key":"659_CR9","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1002\/jgt.22360","volume":"89","author":"N Cohen","year":"2018","unstructured":"Cohen, N., Havet, F., Lochet, W., Nisse, N.: Subdivisions of oriented cycles in digraphs with large chromatic number. J. Graph Theory 89(4), 439\u2013456 (2018)","journal-title":"J. Graph Theory"},{"key":"659_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"659_CR11","volume-title":"Graph Theory, Graduate Texts in Mathematics","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory, Graduate Texts in Mathematics, 4th edn. Springer, Berlin (2012)","edition":"4"},{"key":"659_CR12","series-title":"Texts in Computer Science.","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"659_CR13","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"issue":"4","key":"659_CR14","doi-asserted-by":"publisher","first-page":"29:1","DOI":"10.1145\/2886094","volume":"63","author":"FV Fomin","year":"2016","unstructured":"Fomin, F.V., Lokshtanov, D., Panolan, F., Saurabh, S.: Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM 63(4), 29:1\u201329:60 (2016)","journal-title":"J. ACM"},{"key":"659_CR15","volume-title":"Computers and Intractability. A guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. A guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York (1979)"},{"key":"659_CR16","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proc. of the 43rd ACM Symposium on Theory of Computing (STOC) pp. 479\u2013488 (2011)","DOI":"10.1145\/1993636.1993700"},{"issue":"4","key":"659_CR17","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1002\/jgt.22174","volume":"87","author":"F Havet","year":"2018","unstructured":"Havet, F., Maia, A.K., Mohar, B.: Finding a subdivision of a prescribed digraph of order 4. J. Graph Theory 87(4), 536\u2013560 (2018)","journal-title":"J. Graph Theory"},{"issue":"4","key":"659_CR18","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"659_CR19","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/net.3230120306","volume":"12","author":"A Itai","year":"1982","unstructured":"Itai, A., Perl, Y., Shiloach, Y.: The complexity of finding maximum disjoint paths with length constraints. Networks 12(3), 277\u2013286 (1982)","journal-title":"Networks"},{"issue":"4","key":"659_CR20","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1002\/jgt.22232","volume":"88","author":"R Kim","year":"2018","unstructured":"Kim, R., Kim, S., Ma, J., Park, B.: Cycles with two blocks in $$k$$-chromatic digraphs. J. Graph Theory 88(4), 592\u2013605 (2018)","journal-title":"J. Graph Theory"},{"key":"659_CR21","doi-asserted-by":"crossref","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Divide-and-color. In: Proc. of the 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG). volume 4271 of LNCS pp. 58\u201367 (2006)","DOI":"10.1007\/11917496_6"},{"issue":"1","key":"659_CR22","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.jctb.2005.03.001","volume":"95","author":"M Kriesell","year":"2005","unstructured":"Kriesell, M.: Disjoint $$A$$-paths in digraphs. J. Comb. Theory, Ser. B 95(1), 168\u20132005 (2005)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"659_CR23","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jctb.1993.1018","volume":"57","author":"A Metzlar","year":"1993","unstructured":"Metzlar, A.: Disjoint paths in acyclic digraphs. J. Comb. Theory, Ser. B 57(2), 228\u2013238 (1993)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"659_CR24","first-page":"239","volume":"25","author":"B Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Ann. Discrete Math. 25, 239\u2013254 (1985)","journal-title":"Ann. Discrete Math."},{"key":"659_CR25","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006)"},{"key":"659_CR26","volume-title":"Matroid Theory","author":"JG Oxley","year":"1992","unstructured":"Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)"},{"issue":"2","key":"659_CR27","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1006\/jctb.2000.2029","volume":"82","author":"A Schrijver","year":"2001","unstructured":"Schrijver, A.: A short proof of Mader\u2019s $${\\cal{S}}$$-paths theorem. J. Comb. Theory, Ser. B 82(2), 319\u2013321 (2001)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"659_CR28","volume-title":"Algorithms","author":"R Sedgewick","year":"2011","unstructured":"Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison-Wesley, Boston (2011)","edition":"4"},{"issue":"3","key":"659_CR29","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1016\/j.jcss.2015.11.008","volume":"82","author":"H Shachnai","year":"2016","unstructured":"Shachnai, H., Zehavi, M.: Representative families: a unified tradeoff-based approach. J. Comput. Syst. Sci. 82(3), 488\u2013502 (2016)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"659_CR30","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/070697781","volume":"24","author":"A Slivkins","year":"2010","unstructured":"Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. SIAM J. Discrete Math. 24(1), 146\u2013157 (2010)","journal-title":"SIAM J. Discrete Math."},{"key":"659_CR31","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/S0020-0190(96)00174-3","volume":"60","author":"G Venkatesan","year":"1996","unstructured":"Venkatesan, G., Pandu Rangan, C.: Approximate triclique coloring for register allocation. Inf. Process. Lett. 60, 249\u2013253 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"659_CR32","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1016\/j.ipl.2016.02.005","volume":"116","author":"M Zehavi","year":"2016","unstructured":"Zehavi, M.: A randomized algorithm for long directed cycle. Inf. Process. Lett. 116(6), 419\u2013422 (2016)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00659-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00659-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00659-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,11]],"date-time":"2020-12-11T01:14:06Z","timestamp":1607649246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00659-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,12]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["659"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00659-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,12]]},"assertion":[{"value":"29 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}