{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:53Z","timestamp":1759637753409,"version":"3.41.0"},"publisher-location":"Cham","reference-count":22,"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_6","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"66-79","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths"],"prefix":"10.1007","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"}]},{"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":[[2018,3,13]]},"reference":[{"issue":"4","key":"6_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":"6_CR2","doi-asserted-by":"crossref","unstructured":"Ara\u00fajo, J., Campos, V.A., Maia, A.K., Sau, I., Silva, A.: On the complexity of finding internally vertex-disjoint long directed paths. CoRR, abs\/1706.09066 (2017)","DOI":"10.1007\/978-3-319-77404-6_6"},{"key":"6_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-998-1","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, London (2008). https:\/\/doi.org\/10.1007\/978-1-84800-998-1","edition":"2"},{"key":"6_CR4","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. Theoret. Comput. Sci. 562, 283\u2013303 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"6_CR5","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"},{"issue":"2","key":"6_CR6","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":"6_CR7","unstructured":"Cohen, N., Havet, F., Lochet, W., Nisse, N.: Subdivisions of oriented cycles in digraphs with large chromatic number. CoRR, abs\/1605.07762 (2016)"},{"key":"6_CR8","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, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"6_CR9","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2012","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-662-53622-3","edition":"4"},{"issue":"4","key":"6_CR10","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":"6_CR11","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":"6_CR12","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), pp. 479\u2013488 (2011)","DOI":"10.1145\/1993636.1993700"},{"key":"6_CR13","doi-asserted-by":"publisher","unstructured":"Havet, F., Maia, A.K., Mohar, B.: Finding a subdivision of a prescribed digraph of order 4. J. Graph Theory (to appear). https:\/\/doi.org\/10.1002\/jgt.22174","DOI":"10.1002\/jgt.22174"},{"issue":"3","key":"6_CR14","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"},{"key":"6_CR15","unstructured":"Kim, R., Kim, S.-J., Ma, J., Park, B.: Cycles with two blocks in $$k$$-chromatic digraphs. CoRR, abs\/1610.05839 (2016)"},{"issue":"1","key":"6_CR16","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\u2013172 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"6_CR17","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":"6_CR18","first-page":"239","volume":"25","author":"B Monien","year":"1985","unstructured":"Monien, B.: How to find long paths efficiently. Ann. Discret. Math. 25, 239\u2013254 (1985)","journal-title":"Ann. Discret. Math."},{"issue":"2","key":"6_CR19","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":"6_CR20","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":"6_CR21","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":"6","key":"6_CR22","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":["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_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:28:48Z","timestamp":1751480928000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_6","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"}}]}}