{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T10:15:06Z","timestamp":1672568106693},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T00:00:00Z","timestamp":1519603200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1007\/s10878-018-0266-x","type":"journal-article","created":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T06:21:13Z","timestamp":1519626073000},"page":"965-1006","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The QAP-polytope and the graph isomorphism problem"],"prefix":"10.1007","volume":"36","author":[{"given":"Pawan","family":"Aurora","sequence":"first","affiliation":[]},{"given":"Shashank K.","family":"Mehta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,2,26]]},"reference":[{"key":"266_CR1","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1974","unstructured":"Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley, Reading"},{"key":"266_CR2","unstructured":"Ambler AP, Barrow HG, Brown CM, Burstall RH, Popplestone RJ (1973) A versatile computer-controlled assembly system. In: Proceedings of the 3rd international joint conference on artificial intelligence, pp 298\u2013307"},{"key":"266_CR3","first-page":"66","volume":"86","author":"V Arvind","year":"2005","unstructured":"Arvind V, Tor\u00e1n J (2005) Isomorphism testing: perspective and open problems. Bull EATCS 86:66\u201384","journal-title":"Bull EATCS"},{"key":"266_CR4","doi-asserted-by":"crossref","unstructured":"Atserias A, Maneva EN (2012) Sherali\u2013Adams relaxations and indistinguishability in counting logics. In: Innovations in theoretical computer science 2012. Cambridge, MA, pp 367\u2013379","DOI":"10.1145\/2090236.2090265"},{"key":"266_CR5","doi-asserted-by":"crossref","unstructured":"Babai L (1981) Moderately exponential bound for graph isomorphism. In: Fundamentals of computation theory, FCT\u201981, proceedings of the 1981 international FCT-conference, Szeged, Hungary, pp 34\u201350","DOI":"10.1007\/3-540-10854-8_4"},{"key":"266_CR6","doi-asserted-by":"crossref","unstructured":"Babai L (2014) On the automorphism groups of strongly regular graphs I. In: Innovations in theoretical computer science, ITCS\u201914, Princeton, pp 359\u2013368","DOI":"10.1145\/2554797.2554830"},{"key":"266_CR7","doi-asserted-by":"crossref","unstructured":"Babai L (2016) Graph isomorphism in quasipolynomial time [extended abstract]. In: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC 2016, Cambridge, MA, USA, pp 684\u2013697","DOI":"10.1145\/2897518.2897542"},{"key":"266_CR8","doi-asserted-by":"crossref","unstructured":"Babai L, Chen X, Sun X, Teng S, Wilmes J (2013) Faster canonical forms for strongly regular graphs. In: 54th Annual IEEE symposium on foundations of computer science, FOCS 2013, 26\u201329 October, 2013, Berkeley, CA, USA, pp 157\u2013166","DOI":"10.1109\/FOCS.2013.25"},{"key":"266_CR9","doi-asserted-by":"crossref","unstructured":"Babai L, Grigoryev DY, Mount DM (1982) Isomorphism of graphs with bounded eigenvalue multiplicity. In: STOC, pp 310\u2013324","DOI":"10.1145\/800070.802206"},{"key":"266_CR10","doi-asserted-by":"crossref","unstructured":"Babai L, Luks EM (1983) Canonical labeling of graphs. In: STOC, pp 171\u2013183","DOI":"10.1145\/800061.808746"},{"issue":"4","key":"266_CR11","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"HL Bodlaender","year":"1990","unstructured":"Bodlaender HL (1990) Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J Algorithms 11(4):631\u2013643","journal-title":"J Algorithms"},{"issue":"2","key":"266_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"RB Boppana","year":"1987","unstructured":"Boppana RB, H\u00e5stad J, Zachos S (1987) Does co-np have short interactive proofs? Inf Process Lett 25(2):127\u2013132","journal-title":"Inf Process Lett"},{"issue":"4","key":"266_CR13","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J Cai","year":"1992","unstructured":"Cai J, F\u00fcrer M, Immerman N (1992) An optimal lower bound on the number of variables for graph identifications. Combinatorica 12(4):389\u2013410","journal-title":"Combinatorica"},{"issue":"1","key":"266_CR14","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1137\/0210015","volume":"10","author":"CJ Colbourn","year":"1981","unstructured":"Colbourn CJ, Booth KS (1981) Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J Comput 10(1):203\u2013225","journal-title":"SIAM J Comput"},{"key":"266_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0167-5060(08)70319-4","volume":"2","author":"D Corneil","year":"1978","unstructured":"Corneil D, Mathon R (1978) Algorithmic techniques for the generation and analysis of strongly regular graphs and other combinatorial configurations. Ann Discrete Math 2:1\u201332","journal-title":"Ann Discrete Math"},{"key":"266_CR16","unstructured":"Filotti IS, Mayer JN (1980) A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus (working paper). In: STOC, pp 236\u2013243"},{"key":"266_CR17","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Francisco"},{"key":"266_CR18","doi-asserted-by":"crossref","unstructured":"Grohe M, Marx D (2012) Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In: Proceedings of the 44th symposium on theory of computing conference, STOC 2012, New York, NY, USA, May 19\u201322, 2012, pp 173\u2013192","DOI":"10.1145\/2213977.2213996"},{"key":"266_CR19","unstructured":"Grohe M, Otto M (2012) Pebble games and linear equations. In: Computer science logic (CSL\u201912)\u201426th international workshop\/21st annual conference of the EACSL, CSL 2012, Sept 3\u20136, 2012, Fontainebleau, France, pp 289\u2013304"},{"key":"266_CR20","unstructured":"Hopcroft JE, Tarjan RE (1972) Isomorphism of planar graphs. In: 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, pp 131\u2013152"},{"key":"266_CR21","unstructured":"Hopcroft JE, Wong JK (1974) Linear time algorithm for isomorphism of planar graphs (preliminary report). In: STOC, pp 172\u2013184"},{"key":"266_CR22","unstructured":"J\u00fcnger M, Kaibel V (1997) Box-inequalities for quadratic assignment polytopes. In: Mathematical programming, pp 175\u2013197"},{"key":"266_CR23","doi-asserted-by":"crossref","unstructured":"Kaibel V (1997) Polyhedral combinatorics of the quadratic assignment problem. Ph.D. thesis, Faculty of Mathematics and Natural Sciences, University of Cologne","DOI":"10.1007\/3-540-69346-7_31"},{"key":"266_CR24","doi-asserted-by":"crossref","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: 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, pp 85\u2013103","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"4","key":"266_CR25","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1137\/S0097539789166880","volume":"25","author":"PN Klein","year":"1996","unstructured":"Klein PN (1996) Efficient parallel algorithms for chordal graphs. SIAM J Comput 25(4):797\u2013827","journal-title":"SIAM J Comput"},{"key":"266_CR26","doi-asserted-by":"crossref","unstructured":"K\u00f6bler J, Kuhnert S, Laubner B, Verbitsky O (2010) Interval graphs: canonical representation in logspace. In: Automata, languages and programming, 37th international colloquium, ICALP 2010, Bordeaux, France, July 6\u201310, 2010, proceedings, Part I, pp 384\u2013395","DOI":"10.1007\/978-3-642-14165-2_33"},{"issue":"3","key":"266_CR27","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1137\/S1052623400366802","volume":"11","author":"JB Lasserre","year":"2001","unstructured":"Lasserre JB (2001) Global optimization with polynomials and the problem of moments. SIAM J Optim 11(3):796\u2013817","journal-title":"SIAM J Optim"},{"issue":"2","key":"266_CR28","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"GS Lueker","year":"1979","unstructured":"Lueker GS, Booth KS (1979) A linear time algorithm for deciding interval graph isomorphism. J ACM 26(2):183\u2013195","journal-title":"J ACM"},{"issue":"1","key":"266_CR29","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks EM (1982) Isomorphism of graphs of bounded valence can be tested in polynomial time. J Comput Syst Sci 25(1):42\u201365","journal-title":"J Comput Syst Sci"},{"key":"266_CR30","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.disopt.2014.01.004","volume":"12","author":"PN Malkin","year":"2014","unstructured":"Malkin PN (2014) Sherali\u2013Adams relaxations of graph isomorphism polytopes. Discrete Optim 12:73\u201397","journal-title":"Discrete Optim"},{"issue":"3","key":"266_CR31","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0020-0190(79)90004-8","volume":"8","author":"R Mathon","year":"1979","unstructured":"Mathon R (1979) A note on the graph isomorphism counting problem. Inf Process Lett 8(3):131\u2013132","journal-title":"Inf Process Lett"},{"key":"266_CR32","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2013.09.003","volume":"60","author":"BD McKay","year":"2014","unstructured":"McKay BD, Piperno A (2014) Practical graph isomorphism, II. J Symb Comput 60:94\u2013112","journal-title":"J Symb Comput"},{"key":"266_CR33","doi-asserted-by":"crossref","unstructured":"Miller GL (1980) Isomorphism testing for graphs of bounded genus. In: STOC, pp 225\u2013235","DOI":"10.1145\/800141.804670"},{"key":"266_CR34","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell R, Wright J, Wu C, Zhou Y (2014) Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp 1659\u20131677","DOI":"10.1137\/1.9781611973402.120"},{"key":"266_CR35","first-page":"147","volume":"174","author":"IN Ponomarenko","year":"1988","unstructured":"Ponomarenko IN (1988) Isomorphism problem for classes of graphs closed under contractions. Zapiski Nauchnykh Seminarov POMI 174:147\u2013177","journal-title":"Zapiski Nauchnykh Seminarov POMI"},{"issue":"3","key":"266_CR36","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.disopt.2009.01.002","volume":"6","author":"J Povh","year":"2009","unstructured":"Povh J, Rendl F (2009) Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim 6(3):231\u2013241","journal-title":"Discrete Optim"},{"issue":"3","key":"266_CR37","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1016\/0022-0000(88)90010-4","volume":"37","author":"U Sch\u00f6ning","year":"1988","unstructured":"Sch\u00f6ning U (1988) Graph isomorphism is in the low hierarchy. J Comput Syst Sci 37(3):312\u2013323","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"266_CR38","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/0403036","volume":"3","author":"HD Sherali","year":"1990","unstructured":"Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J Discrete Math 3(3):411\u2013430","journal-title":"SIAM J Discrete Math"},{"key":"266_CR39","unstructured":"Snook A, Schoenebeck G, Codenotti P (2014) Graph isomorphism and the lasserre hierarchy. CoRR. arXiv:1401.0758"},{"key":"266_CR40","unstructured":"Spence E Strongly regular graphs. http:\/\/www.maths.gla.ac.uk\/~es\/srgraphs.php . Accessed 1 January 2018"},{"key":"266_CR41","doi-asserted-by":"crossref","unstructured":"Spielman DA (1996) Faster isomorphism testing of strongly regular graphs. In: Proceedings of the twenty-eighth annual ACM symposium on the theory of computing, Philadelphia, Pennsylvania, USA, May 22\u201324, pp 576\u2013584","DOI":"10.1145\/237814.238006"},{"key":"266_CR42","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1021\/c160016a007","volume":"5","author":"EH Sussenguth Jr","year":"1965","unstructured":"Sussenguth EH Jr (1965) A graph-theoretic algorithm for matching chemical structures. J Chem Doc 5:36\u201343","journal-title":"J Chem Doc"},{"issue":"2\u20133","key":"266_CR43","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0166-218X(91)90049-3","volume":"30","author":"G Tinhofer","year":"1991","unstructured":"Tinhofer G (1991) A note on compact graphs. Discrete Appl Math 30(2\u20133):253\u2013264","journal-title":"Discrete Appl Math"},{"key":"266_CR44","doi-asserted-by":"crossref","unstructured":"Uehara R (2008) Simple geometrical intersection graphs. In: WALCOM: algorithms and computation, second international workshop, WALCOM 2008, Dhaka, Bangladesh, February 7\u20138, pp 25\u201333","DOI":"10.1007\/978-3-540-77891-2_3"},{"issue":"9","key":"266_CR45","first-page":"12","volume":"2","author":"B Weisfeiler","year":"1968","unstructured":"Weisfeiler B, Lehman AA (1968) A reduction of a graph to a canonical form and an algebra arising during this reduction (in russian). Nauchno-Technicheskaya Informatsia Seriya 2(9):12\u201316","journal-title":"Nauchno-Technicheskaya Informatsia Seriya"},{"key":"266_CR46","first-page":"83","volume":"118","author":"V Zeml\u2019ahenko","year":"1982","unstructured":"Zeml\u2019ahenko V, Korneyenko N, Tyshkevich RI (1982) Graph isomorphism problem. Zapiski Nauchnykh Seminarov POMI 118:83\u2013158","journal-title":"Zapiski Nauchnykh Seminarov POMI"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0266-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0266-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0266-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T20:43:26Z","timestamp":1570826606000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0266-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,26]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,10]]}},"alternative-id":["266"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0266-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,26]]},"assertion":[{"value":"26 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}