{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T04:06:14Z","timestamp":1780373174297,"version":"3.54.1"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032272416","type":"print"},{"value":"9783032272423","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-27242-3_36","type":"book-chapter","created":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T03:30:39Z","timestamp":1780371039000},"page":"614-630","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Graph Isomorphism: Mixed-Integer Convex Optimization from\u00a0First-Order Methods"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-5555-8245","authenticated-orcid":false,"given":"Wenjie","family":"Xiao","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6284-3033","authenticated-orcid":false,"given":"Mathieu","family":"Besan\u00e7on","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3645-9513","authenticated-orcid":false,"given":"Patrick","family":"Gel\u00df","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0705-1356","authenticated-orcid":false,"given":"Deborah","family":"Hendrych","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9672-3806","authenticated-orcid":false,"given":"Stefan","family":"Klus","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7365-3000","authenticated-orcid":false,"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,1]]},"reference":[{"key":"36_CR1","unstructured":"PACE challenge 2023: Twinwidth. PACE 2023 challenge on computing low-width contraction sequences; exact and heuristic tracks (2023). https:\/\/pacechallenge.org\/2023\/"},{"issue":"10","key":"36_CR2","doi-asserted-by":"publisher","first-page":"2942","DOI":"10.1073\/pnas.1401651112","volume":"112","author":"Y Aflalo","year":"2015","unstructured":"Aflalo, Y., Bronstein, A., Kimmel, R.: On convex relaxation of graph isomorphism. Proc. Natl. Acad. Sci. 112(10), 2942\u20132947 (2015)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"3","key":"36_CR3","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1007\/s10878-018-0266-x","volume":"36","author":"P Aurora","year":"2018","unstructured":"Aurora, P., Mehta, S.K.: The QAP-polytope and the graph isomorphism problem. J. Comb. Optim. 36(3), 965\u20131006 (2018). https:\/\/doi.org\/10.1007\/s10878-018-0266-x","journal-title":"J. Comb. Optim."},{"key":"36_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L.: Group, graphs, algorithms: the graph isomorphism problem. In: Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pp. 3319\u20133336. World Scientific (2018)","DOI":"10.1142\/9789813272880_0183"},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L., Grigoryev, D.Y., Mount, D.M.: Isomorphism of graphs with bounded eigenvalue multiplicity. In: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pp. 310\u2013324 (1982)","DOI":"10.1145\/800070.802206"},{"key":"36_CR6","doi-asserted-by":"crossref","unstructured":"Besan\u00e7on, M., Carderera, A., Pokutta, S.: FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and conditional gradients. INFORMS J. Comput. (2022)","DOI":"10.1287\/ijoc.2022.1191.cd"},{"key":"36_CR7","doi-asserted-by":"crossref","unstructured":"Besan\u00e7on, M., et al.: Improved algorithms and novel applications of the FrankWolfe.jl library. ACM Trans. Math. Software (2025)","DOI":"10.1145\/3765626"},{"key":"36_CR8","doi-asserted-by":"crossref","unstructured":"Bestuzheva, K., et\u00a0al.: Enabling research through the SCIP Optimization Suite 8.0. ACM Trans. Math. Software 49(2), 1\u201321 (2023)","DOI":"10.1145\/3585516"},{"key":"36_CR9","unstructured":"Bolusani, S., et al.: The SCIP Optimization Suite 9.0. Technical report, Optimization Online (2024). https:\/\/optimization-online.org\/2024\/02\/the-scip-optimization-suite-9-0\/"},{"key":"36_CR10","unstructured":"Braun, G., et al.: Conditional Gradient Methods. MOS-SIAM Series on Optimization (2025)"},{"key":"36_CR11","unstructured":"Braun, G., Pokutta, S., Zink, D.: Lazifying conditional gradient algorithms. In: International Conference on Machine Learning, pp. 566\u2013575. PMLR (2017)"},{"key":"36_CR12","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. J. Exper. Algorithmics (JEA) 18, 3:1\u20133:21 (2013)","DOI":"10.1145\/2543629"},{"key":"36_CR13","doi-asserted-by":"crossref","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logistics Q. 3, 95\u2013110 (1956). https:\/\/onlinelibrary.wiley.com\/doi\/abs\/10.1002\/nav.3800030109","DOI":"10.1002\/nav.3800030109"},{"issue":"3","key":"36_CR14","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"ML Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM (JACM) 34(3), 596\u2013615 (1987)","journal-title":"J. ACM (JACM)"},{"key":"36_CR15","unstructured":"Garber, D., Meshi, O.: Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes. In: Advances in Neural Information Processing Systems, vol. 29 (2016)"},{"issue":"4","key":"36_CR16","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/s10898-016-0450-4","volume":"67","author":"AM Gleixner","year":"2017","unstructured":"Gleixner, A.M., Berthold, T., M\u00fcller, B., Weltge, S.: Three enhancements for optimization-based bound tightening. J. Global Optim. 67(4), 731\u2013757 (2017)","journal-title":"J. Global Optim."},{"key":"36_CR17","doi-asserted-by":"publisher","unstructured":"Grohe, M., Schweitzer, P.: The graph isomorphism problem. Commun. ACM 63(10), 128\u2013134 (2020). https:\/\/doi.org\/10.1145\/3372123","DOI":"10.1145\/3372123"},{"key":"36_CR18","unstructured":"Hendrych, D., Besan\u00e7on, M., Mart\u00ednez-Rubio, D., Pokutta, S.: Secant line search for Frank-Wolfe algorithms. In: Forty-second International Conference on Machine Learning (2025)"},{"key":"36_CR19","doi-asserted-by":"publisher","unstructured":"Hendrych, D., Besan\u00e7on, M., Pokutta, S.: Solving the optimal experiment design problem with mixed-integer convex methods. In: Proceedings of the Symposium on Experimental Algorithms (2024). https:\/\/doi.org\/10.4230\/LIPIcs.SEA.2024.16","DOI":"10.4230\/LIPIcs.SEA.2024.16"},{"key":"36_CR20","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1007\/s12532-025-00288-w","volume":"17","author":"D Hendrych","year":"2025","unstructured":"Hendrych, D., Troppens, H., Besan\u00e7on, M., Pokutta, S.: Convex mixed-integer optimization with Frank-Wolfe methods. Math. Program. Comput. 17, 731\u2013757 (2025)","journal-title":"Math. Program. Comput."},{"key":"36_CR21","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E., Tarjan, R.E.: Isomorphism of planar graphs. In: Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations, held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department, pp. 131\u2013152. Springer (1972)","DOI":"10.1007\/978-1-4684-2001-2_13"},{"key":"36_CR22","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1093\/imaiai\/iay001","volume":"7","author":"S Klus","year":"2018","unstructured":"Klus, S., Sahai, T.: A spectral assignment approach for the graph isomorphism problem. Inf. Infer. A J. IMA 7, 689\u2013706 (2018). https:\/\/doi.org\/10.1093\/imaiai\/iay001","journal-title":"Inf. Infer. A J. IMA"},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"Klus, S., Gel\u00df, P.: Continuous optimization methods for the graph isomorphism problem. Inf. Inference: A J. IMA 14(2), iaaf011 (2025)","DOI":"10.1093\/imaiai\/iaaf011"},{"issue":"1\u20132","key":"36_CR24","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/nav.3800020109","volume":"2","author":"HW Kuhn","year":"1955","unstructured":"Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logistics Q. 2(1\u20132), 83\u201397 (1955)","journal-title":"Naval Res. Logistics Q."},{"key":"36_CR25","unstructured":"Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of Frank-Wolfe optimization variants. In: Advances in Neural Information Processing Systems, vol. 28 (2015)"},{"key":"36_CR26","doi-asserted-by":"crossref","unstructured":"Levitin, E., Polyak, B.: Constrained minimization methods. USSR Comput. Math. Math. Phys. 6, 1\u201350 (1966). https:\/\/www.sciencedirect.com\/science\/article\/pii\/0041555366901145","DOI":"10.1016\/0041-5553(66)90114-5"},{"issue":"1","key":"36_CR27","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25(1), 42\u201365 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"36_CR28","unstructured":"Maskan, H., Hou, Y., Sra, S., Yurtsever, A.: Revisiting Frank-Wolfe for structured nonconvex optimization. arXiv preprint arXiv:2503.08921 (2025)"},{"key":"36_CR29","unstructured":"McKay, B., Piperno, A.: Nauty and traces benchmark graph libraries. https:\/\/pallini.di.uniroma1.it\/Graphs.html (2025), collections of benchmark graphs (DIMACS and dreadnaut formats); current version 2_9_1 (2025)"},{"key":"36_CR30","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","volume":"60","author":"BD McKay","year":"2014","unstructured":"McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symb. Comput. 60, 94\u2013112 (2014)","journal-title":"J. Symb. Comput."},{"key":"36_CR31","unstructured":"McKay, B.D., et\u00a0al.: Practical graph isomorphism (1981)"},{"issue":"1","key":"36_CR32","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1137\/0105003","volume":"5","author":"J Munkres","year":"1957","unstructured":"Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32\u201338 (1957)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"1","key":"36_CR33","first-page":"1","volume":"44","author":"J Pena","year":"2019","unstructured":"Pena, J., Rodriguez, D.: Polytope conditioning and linear convergence of the Frank-Wolfe algorithm. Math. Oper. Res. 44(1), 1\u201318 (2019)","journal-title":"Math. Oper. Res."},{"key":"36_CR34","unstructured":"Pokutta, S.: Scalable DC optimization via adaptive Frank-Wolfe algorithms. arXiv preprint arXiv:2507.17545 (2025). https:\/\/arxiv.org\/abs\/2507.17545"},{"key":"36_CR35","doi-asserted-by":"crossref","unstructured":"Read, R., Corneil, D.: The graph isomorphism disease. J. Graph Theory 1, 339\u2013363 (1977). https:\/\/onlinelibrary.wiley.com\/doi\/abs\/10.1002\/jgt.3190010410","DOI":"10.1002\/jgt.3190010410"},{"issue":"4","key":"36_CR36","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1002\/jgt.3190010410","volume":"1","author":"RC Read","year":"1977","unstructured":"Read, R.C., Corneil, D.G.: The graph isomorphism disease. J. Graph Theory 1(4), 339\u2013363 (1977)","journal-title":"J. Graph Theory"},{"key":"36_CR37","unstructured":"Tsuji, K., Tanaka, K., Pokutta, S.: Sparser kernel herding with pairwise conditional gradients without swap steps. arXiv preprint arXiv:2110.12650 (2021)"},{"issue":"6","key":"36_CR38","doi-asserted-by":"publisher","first-page":"2399","DOI":"10.1109\/TNET.2021.3088327","volume":"29","author":"V Valls","year":"2021","unstructured":"Valls, V., Iosifidis, G., Tassiulas, L.: Birkhoff\u2019s decomposition revisited: sparse scheduling for high-speed circuit switches. IEEE\/ACM Trans. Networking 29(6), 2399\u20132412 (2021)","journal-title":"IEEE\/ACM Trans. Networking"},{"issue":"4","key":"36_CR39","doi-asserted-by":"publisher","first-page":"1426","DOI":"10.1007\/BF02104746","volume":"29","author":"VN Zemlyachenko","year":"1985","unstructured":"Zemlyachenko, V.N., Korneenko, N.M., Tyshkevich, R.I.: Graph isomorphism problem. J. Sov. Math. 29(4), 1426\u20131481 (1985)","journal-title":"J. Sov. Math."}],"container-title":["Lecture Notes in Computer Science","Integration of Constraint Programming, Artificial Intelligence, and Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27242-3_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T03:30:45Z","timestamp":1780371045000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27242-3_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032272416","9783032272423"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27242-3_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"1 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"CPAIOR","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rabat","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Morocco","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 May 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cpaior2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sites.google.com\/view\/cpaior2026\/home","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}