{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:19:42Z","timestamp":1759666782187,"version":"3.37.3"},"reference-count":20,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"content-version":"vor","delay-in-days":22,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"funder":[{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"crossref","award":["303958\/2015-4"],"award-info":[{"award-number":["303958\/2015-4"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["425778\/2016-9"],"award-info":[{"award-number":["425778\/2016-9"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004586","name":"FAPERJ","doi-asserted-by":"crossref","award":["E-26\/202.854\/2017"],"award-info":[{"award-number":["E-26\/202.854\/2017"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004586","name":"FAPERJ","doi-asserted-by":"crossref","award":["E-26\/200.330\/2020"],"award-info":[{"award-number":["E-26\/200.330\/2020"]}],"id":[{"id":"10.13039\/501100004586","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["001"],"award-info":[{"award-number":["001"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2021,1,14]]},"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:p>The longest induced path problem consists in finding a maximum subset of vertices of a graph such that it induces a simple path. We propose a new exact enumerative algorithm that solves problems with up to 138 vertices and 493 edges and a heuristic for larger problems. Detailed computational experiments compare the results obtained by the new algorithms with other approaches in the literature and investigate the characteristics of the optimal solutions.<\/jats:p>","DOI":"10.1051\/ro\/2021004","type":"journal-article","created":{"date-parts":[[2021,1,15]],"date-time":"2021-01-15T09:56:21Z","timestamp":1610704581000},"page":"333-353","source":"Crossref","is-referenced-by-count":4,"title":["Exact and approximate algorithms for the longest induced path problem"],"prefix":"10.1051","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1766-6461","authenticated-orcid":false,"given":"Rusl\u00e1n G.","family":"Marzo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9478-2351","authenticated-orcid":false,"given":"Celso C.","family":"Ribeiro","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Ahuja R.K., Magnanti T.L. and Orlin J.B., Network flows. Elsevier (1988).","DOI":"10.21236\/ADA594171"},{"key":"R2","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/BF01788684","volume":"5","author":"Alles","year":"1989","journal-title":"Graphs Comb."},{"key":"R3","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"Barab\u00e1si","year":"1999","journal-title":"Science"},{"key":"R4","unstructured":"Bergougnoux B. and Kant\u00e9 M.M., A meta-algorithm for solving connectivity and acyclicity constraints on locally checkable properties parameterized by graph width measures. Preprint arXiv:1805.11275 (2018)."},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B\u00f6kler F., Chimani M., Wagner M.H. and Wiedera T., An experimental study of ILP formulations for the longest induced path problem. In Combinatorial Optimization, edited by Ba\u00efou M., Gendron B., G\u00fcnl\u00fck O. and Mahjoub A.R.. In Vol. 12176 of Lecture Notes in Computer Science. Springer, Cham (2020).","DOI":"10.1007\/978-3-030-53262-8_8"},{"key":"R6","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman and Co., New York (1979)."},{"key":"R7","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0020-0190(01)00222-8","volume":"81","author":"Gavril","year":"2002","journal-title":"Inf. Process. Lett."},{"key":"R8","doi-asserted-by":"crossref","first-page":"3057","DOI":"10.1016\/j.dam.2008.01.019","volume":"156","author":"Ishizeki","year":"2008","journal-title":"Discrete Appl. Math."},{"key":"R9","unstructured":"Jaffke L., Kwon O.-J. and Telle J., Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width. In: Vol. 89 of Leibniz International Proceedings in Informatics (2018) 1\u201321."},{"key":"R10","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.dam.2019.06.026","volume":"278","author":"Jaffke","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"R11","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1109\/TEC.1958.5222529","volume":"7","author":"Kautz","year":"1958","journal-title":"IRE Trans. Electron. Comput."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Kratsch D., M\u00fcller H. and Todinca I., Feedback vertex set and longest induced path on AT-free graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science. Springer (2003) 309\u2013321.","DOI":"10.1007\/978-3-540-39890-5_27"},{"key":"R13","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1016\/j.ejor.2019.04.011","volume":"278","author":"Matsypura","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"R14","unstructured":"Moviegalaxies, Social networks in movies. Available from: https:\/\/moviegalaxies.com\/ (2020)."},{"key":"R15","unstructured":"NetworkX developers, NetworkX documentation. Available from: http:\/\/networkx.github.io\/(2020)."},{"key":"R16","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"Newman","year":"2003","journal-title":"SIAM Rev."},{"key":"R17","unstructured":"PassMark, PassMark Software \u2013 CPU Benchmarks. Intel Core i5-4460S vs. Intel Xeon E5-1650 v2 vs. Intel Xeon Gold 6134. Available from: https:\/\/www.cpubenchmark.net\/compare\/Intel-i5-4460S-vs-Intel-Xeon-E5-1650-v2-vs-Intel-Xeon-Gold-6134\/2232vs2066vs3008 (2020)."},{"key":"R18","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1098\/rspl.1895.0041","volume":"58","author":"Pearson","year":"1895","journal-title":"Proc. R. Soc. London"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Prokhorenkova L.O. and Samosvat E., Global clustering coefficient in scale-free networks. In: International Workshop on Algorithms and Models for the Web-Graph. Springer (2014) 47\u201358.","DOI":"10.1007\/978-3-319-13123-8_5"},{"key":"R20","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2021004\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T09:09:27Z","timestamp":1616490567000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2021004"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3]]},"references-count":20,"journal-issue":{"issue":"2"},"alternative-id":["ro200477"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2021004","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2021,3]]}}}