{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:24:36Z","timestamp":1743132276669,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030532611"},{"type":"electronic","value":"9783030532628"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-53262-8_8","type":"book-chapter","created":{"date-parts":[[2020,7,21]],"date-time":"2020-07-21T23:12:23Z","timestamp":1595373143000},"page":"89-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["An Experimental Study of ILP Formulations for the Longest Induced Path Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7950-6965","authenticated-orcid":false,"given":"Fritz","family":"B\u00f6kler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4681-5550","authenticated-orcid":false,"given":"Markus","family":"Chimani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4593-8740","authenticated-orcid":false,"given":"Mirko H.","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5923-4114","authenticated-orcid":false,"given":"Tilo","family":"Wiedera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,22]]},"reference":[{"issue":"1","key":"8_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-008-0001-1","volume":"1","author":"T Achterberg","year":"2009","unstructured":"Achterberg, T.: SCIP: solving constraint integer programs. Math. Program. Comput. 1(1), 1\u201341 (2009)","journal-title":"Math. Program. Comput."},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of scaling in random networks. Science 286, 509\u2013512 (1999)","journal-title":"Science"},{"key":"8_CR3","volume-title":"Network Science","author":"AL Barab\u00e1si","year":"2016","unstructured":"Barab\u00e1si, A.L.: Network Science. Cambridge University Press, Cambridge (2016)"},{"issue":"3","key":"8_CR4","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1016\/j.ejor.2013.07.038","volume":"236","author":"T Bekta\u015f","year":"2014","unstructured":"Bekta\u015f, T., Gouveia, L.: Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? EJOR 236(3), 820\u2013832 (2014)","journal-title":"EJOR"},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P Berman","year":"1992","unstructured":"Berman, P., Schnitger, G.: On the complexity of approximating the independent set problem. Inf. Comput. 96(1), 77\u201394 (1992)","journal-title":"Inf. Comput."},{"issue":"2","key":"8_CR6","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"HL Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms 18(2), 238\u2013255 (1995)","journal-title":"J. Algorithms"},{"key":"8_CR7","volume-title":"Analyzing Social Networks","author":"SP Borgatti","year":"2013","unstructured":"Borgatti, S.P., Everett, M.G., Johnson, J.C.: Analyzing Social Networks. SAGE Publishing, Thousand Oaks (2013)"},{"issue":"3","key":"8_CR8","first-page":"61","volume":"3","author":"F Buckley","year":"1988","unstructured":"Buckley, F., Harary, F.: On longest induced paths in graphs. Chin. Quart. J. Math. 3(3), 61\u201365 (1988)","journal-title":"Chin. Quart. J. Math."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"B\u00f6kler, F., Chimani, M., Wagner, M.H., Wiedera, T.: An experimental study of ILP formulations for the longest induced path problem (2020). arXiv:2002.07012 [cs.DS]","DOI":"10.1007\/978-3-030-53262-8_8"},{"key":"8_CR10","doi-asserted-by":"crossref","unstructured":"Chen, Y., Flum, J.: On parameterized path and chordless path problems. In: CCC, pp. 250\u2013263 (2007)","DOI":"10.1109\/CCC.2007.21"},{"key":"8_CR11","unstructured":"Chimani, M., Gutwenger, C., Juenger, M., Klau, G.W., Klein, K., Mutzel, P.: The open graph drawing framework (OGDF). In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 543\u2013569. Chapman and Hall\/CRC (2013). www.ogdf.net"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Chimani, M., Kandyba, M., Ljubi\u0107, I., Mutzel, P.: Obtaining optimal $$k$$-cardinality trees fast. J. Exp. Algorithmics 14, 5:2.5\u20135:2.23 (2010)","DOI":"10.1145\/1498698.1537600"},{"key":"8_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-540-85097-7_18","volume-title":"Combinatorial Optimization and Applications","author":"M Chimani","year":"2008","unstructured":"Chimani, M., Kandyba, M., Ljubi\u0107, I., Mutzel, P.: Strong formulations for 2-node-connected Steiner network problems. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol. 5165, pp. 190\u2013200. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85097-7_18"},{"key":"8_CR14","first-page":"1","volume":"1695","author":"G Csardi","year":"2006","unstructured":"Csardi, G., Nepusz, T.: The igraph software package for complex network research. InterJ. Complex Syst. 1695, 1\u20139 (2006). http:\/\/igraph.sf.net","journal-title":"InterJ. Complex Syst."},{"key":"8_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-17517-6_36","volume-title":"Algorithms and Computation","author":"D Eppstein","year":"2010","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010. LNCS, vol. 6506, pp. 403\u2013414. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17517-6_36"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BF01586946","volume":"51","author":"M Fischetti","year":"1991","unstructured":"Fischetti, M.: Facets of two Steiner arborescence polyhedra. Math. Program. 51, 401\u2013419 (1991)","journal-title":"Math. Program."},{"key":"8_CR17","series-title":"Combinatorial Optimization","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/0-306-48213-4_13","volume-title":"The Traveling Salesman Problem and Its Variations","author":"M Fischetti","year":"2007","unstructured":"Fischetti, M., Salazar-Gonzalez, J.J., Toth, P.: The generalized traveling salesman and orienteering problems. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variations. Combinatorial Optimization, vol. 12, pp. 609\u2013662. Springer, Boston (2007). https:\/\/doi.org\/10.1007\/0-306-48213-4_13"},{"key":"8_CR18","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 & Co., San Francisco (1979)"},{"issue":"4","key":"8_CR19","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0020-0190(01)00222-8","volume":"81","author":"F Gavril","year":"2002","unstructured":"Gavril, F.: Algorithms for maximum weight induced paths. Inf. Process. Lett. 81(4), 203\u2013208 (2002)","journal-title":"Inf. Process. Lett."},{"key":"8_CR20","unstructured":"Gleixner, A., et al.: The SCIP optimization suite 6.0. ZIB-Report 18-26, Zuse Institute Berlin (2018). https:\/\/scip.zib.de"},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01582064","volume":"63","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X.: The steiner tree polytope and related polyhedra. Math. Program. 63, 157\u2013182 (1994)","journal-title":"Math. Program."},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230230104","volume":"23","author":"MX Goemans","year":"1993","unstructured":"Goemans, M.X., Myung, Y.S.: A catalog of Steiner tree formulations. Networks 23, 19\u201328 (1993)","journal-title":"Networks"},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.dam.2013.12.008","volume":"167","author":"PA Golovach","year":"2014","unstructured":"Golovach, P.A., Paulusma, D., Song, J.: Coloring graphs without short cycles and long induced paths. Discrete Appl. Math. 167, 107\u2013120 (2014)","journal-title":"Discrete Appl. Math."},{"key":"8_CR24","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2. Springer, Heidelberg (1988)"},{"issue":"1","key":"8_CR25","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1 - \\epsilon }$$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"8_CR26","unstructured":"Jackson, M.O.: Social and Economic Networks. Princeton University Press, Princeton (2010)"},{"key":"8_CR27","unstructured":"Jaffke, L., Kwon, O., Telle, J.A.: Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-Width. In: IPEC. LIPIcs, vol. 89, pp. 21:1\u201313 (2017)"},{"key":"8_CR28","unstructured":"Kaminski, J., Schober, M., Albaladejo, R., Zastupailo, O., Hidalgo, C.: Moviegalaxies - Social Networks in Movies. Harvard Dataverse, V3 (2018)"},{"issue":"4","key":"8_CR29","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.ipl.2003.07.004","volume":"88","author":"V Lozin","year":"2003","unstructured":"Lozin, V., Rautenbach, D.: Some results on graphs without long induced paths. Inf. Process. Lett. 88(4), 167\u2013171 (2003)","journal-title":"Inf. Process. Lett."},{"key":"8_CR30","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1016\/j.ejor.2019.04.011","volume":"278","author":"D Matsypura","year":"2019","unstructured":"Matsypura, D., Veremyev, A., Prokopyev, O.A., Pasiliao, E.L.: On exact solution approaches for the longest induced path problem. EJOR 278, 546\u2013562 (2019)","journal-title":"EJOR"},{"issue":"1","key":"8_CR31","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3(1), 23\u201328 (1965)","journal-title":"Israel J. Math."},{"key":"8_CR32","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity - Graphs, Structures, and Algorithms","author":"J Nesetril","year":"2012","unstructured":"Nesetril, J., de Mendez, P.O.: Sparsity - Graphs, Structures, and Algorithms. Algorithms and Combinatorics, vol. 28. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4"},{"key":"8_CR33","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001","volume-title":"Networks: An Introduction","author":"M Newman","year":"2010","unstructured":"Newman, M.: Networks: An Introduction. Oxford University Press, Oxford (2010)"},{"key":"8_CR34","unstructured":"Polzin, T.: Algorithms for the Steiner problem in networks. Ph.D. thesis, Saarland University, Saarbr\u00fccken, Germany (2003)"},{"key":"8_CR35","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1999","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1999)"},{"key":"8_CR36","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-319-11812-3_27","volume-title":"Discovery Science","author":"T Uno","year":"2014","unstructured":"Uno, T., Satoh, H.: An efficient algorithm for enumerating chordless cycles and chordless paths. In: D\u017eeroski, S., Panov, P., Kocev, D., Todorovski, L. (eds.) DS 2014. LNCS (LNAI), vol. 8777, pp. 313\u2013324. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11812-3_27"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-53262-8_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T18:08:38Z","timestamp":1710266918000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-53262-8_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030532611","9783030532628"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-53262-8_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"22 July 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ISCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Montreal, QC","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 May 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 May 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"isco2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.lamsade.dauphine.fr\/~isco\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Symposia","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"66","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.26","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.85","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}