{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T08:47:07Z","timestamp":1743842827849,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,9,4]],"date-time":"2017-09-04T00:00:00Z","timestamp":1504483200000},"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":["Math. Prog. Comp."],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s12532-017-0124-3","type":"journal-article","created":{"date-parts":[[2017,9,4]],"date-time":"2017-09-04T06:47:55Z","timestamp":1504507675000},"page":"143-185","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Detecting almost symmetries of graphs"],"prefix":"10.1007","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3694-6274","authenticated-orcid":false,"given":"Ben","family":"Knueven","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5636-555X","authenticated-orcid":false,"given":"Jim","family":"Ostrowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,4]]},"reference":[{"key":"124_CR1","doi-asserted-by":"crossref","unstructured":"Arvind, V., K\u00f6bler, J., Kuhnert, S., Vasudev, Y.: Approximate graph isomorphism. In: Mathematical Foundations of Computer Science 2012, pp. 100\u2013111. Springer (2012)","DOI":"10.1007\/978-3-642-32589-2_12"},{"key":"124_CR2","doi-asserted-by":"crossref","unstructured":"Babai, L.: Graph isomorphism in quasipolynomial time. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pp. 684\u2013697, New York, NY, USA. ACM (2016)","DOI":"10.1145\/2897518.2897542"},{"key":"124_CR3","doi-asserted-by":"crossref","unstructured":"Buchheim, C., J\u00fcnger, M.: An integer programming approach to fuzzy symmetry detection. In: International Symposium on Graph Drawing, pp. 166\u2013177. Springer (2003)","DOI":"10.1007\/978-3-540-24595-7_16"},{"key":"124_CR4","unstructured":"Culberson, J., Johnson, D., Lewandowski, G., Trick, M.: Graph coloring instances. http:\/\/mat.gsia.cmu.edu\/COLOR\/instances.html , Mar 2015"},{"key":"124_CR5","doi-asserted-by":"crossref","unstructured":"Darga, P.T., Sakallah, K.A., Markov, I.L.: Faster symmetry discovery using sparsity of symmetries. In: Proceedings of the 45th Annual Design Automation Conference, DAC \u201908, pp. 149\u2013154, New York, NY, USA. ACM (2008)","DOI":"10.1145\/1391469.1391509"},{"issue":"4","key":"124_CR6","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s12532-015-0087-1","volume":"7","author":"J Eckstein","year":"2015","unstructured":"Eckstein, J., Hart, W.E., Phillips, C.A.: PEBBL: an object-oriented framework for scalable parallel branch and bound. Math. Program. Comput. 7(4), 429\u2013469 (2015)","journal-title":"Math. Program. Comput."},{"issue":"3","key":"124_CR7","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01895716","volume":"14","author":"P Erd\u0151s","year":"1963","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: Asymmetric graphs. Acta Math. Hung. 14(3), 295\u2013315 (1963)","journal-title":"Acta Math. Hung."},{"key":"124_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U.: Relations between average case complexity and approximation complexity. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pp. 534\u2013543. ACM (2002)","DOI":"10.1145\/509907.509985"},{"key":"124_CR9","unstructured":"Feige, U., Kilian, J.: Zero knowledge and the chromatic number. In: Proceedings of the Eleventh Annual IEEE Conference on Computational Complexity, 1996, pp. 278\u2013287. IEEE (1996)"},{"key":"124_CR10","unstructured":"Fox, M., Long, D., Porteous, J.: Discovering near symmetry in graphs. In: Proceedings of the 22nd National Conference on Artificial Intelligence, vol. 1, pp. 415\u2013420. AAAI Press (2007)"},{"key":"124_CR11","unstructured":"F\u00fcrstenberg, C.: A drawing of a graph. http:\/\/en.wikipedia.org\/wiki\/Graph_theory#mediaviewer\/File:6n-graf.svg , Mar (2015)"},{"key":"124_CR12","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47\u201363. ACM (1974)","DOI":"10.1145\/800119.803884"},{"issue":"3","key":"124_CR13","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1145\/116825.116852","volume":"38","author":"O Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. J ACM 38(3), 690\u2013728 (1991)","journal-title":"J ACM"},{"key":"124_CR14","volume-title":"The Stanford GraphBase: A Platform for Combinatorial Computing","author":"DE Knuth","year":"1993","unstructured":"Knuth, D.E.: The Stanford GraphBase: A Platform for Combinatorial Computing, vol. 37. Addison-Wesley, Reading (1993)"},{"issue":"1\u20132","key":"124_CR15","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. Nav. Res. Log. Q 2(1\u20132), 83\u201397 (1955)","journal-title":"Nav. Res. Log. Q"},{"key":"124_CR16","doi-asserted-by":"crossref","unstructured":"Lin, C.-L.: Hardness of approximating graph transformation problem. In: Algorithms and Computation, pp. 74\u201382. Springer (1994)","DOI":"10.1007\/3-540-58325-4_168"},{"issue":"1","key":"124_CR17","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-002-0358-2","volume":"94","author":"F Margot","year":"2002","unstructured":"Margot, F.: Pruning by isomorphism in branch-and-cut. Math. Program. 94(1), 71\u201390 (2002)","journal-title":"Math. Program."},{"issue":"1\u20133","key":"124_CR18","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-003-0394-6","volume":"98","author":"F Margot","year":"2003","unstructured":"Margot, F.: Exploiting orbits in symmetric ILP. Math. Program. 98(1\u20133), 3\u201321 (2003)","journal-title":"Math. Program."},{"key":"124_CR19","unstructured":"Markov, I.: Almost-symmetries of graphs. In: Proceedings of International Symmetry Conference (ISC), pp. 60\u201370 (2007)"},{"issue":"3","key":"124_CR20","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.: A note on the graph isomorphism counting problem. Inf. Process. Lett. 8(3), 131\u2013136 (1979)","journal-title":"Inf. Process. Lett."},{"key":"124_CR21","unstructured":"McKay, B.D.: Practical Graph Isomorphism. Department of Computer Science, Vanderbilt University (1981)"},{"key":"124_CR22","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":"124_CR23","unstructured":"McKay, B.D., Piperno, A.: Nauty traces\u2014graphs. http:\/\/pallini.di.uniroma1.it\/Graphs.html , Mar (2015)"},{"issue":"1","key":"124_CR24","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."},{"key":"124_CR25","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, R., Wright, J., Wu, C., Zhou, Y.: 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, pp. 1659\u20131677. SIAM (2014)","DOI":"10.1137\/1.9781611973402.120"},{"issue":"1","key":"124_CR26","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s10107-009-0273-x","volume":"126","author":"J Ostrowski","year":"2011","unstructured":"Ostrowski, J., Linderoth, J., Rossi, F., Smriglio, S.: Orbital branching. Math. Program. 126(1), 147\u2013178 (2011)","journal-title":"Math. Program."},{"issue":"4","key":"124_CR27","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. Gr. Theory 1(4), 339\u2013363 (1977)","journal-title":"J. Gr. Theory"},{"key":"124_CR28","unstructured":"Stachniss, C.: C implementation of the Hungarian method. http:\/\/www2.informatik.uni-freiburg.de\/~stachnis\/misc.html , Mar (2015)"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s12532-017-0124-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-017-0124-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-017-0124-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T23:29:45Z","timestamp":1570058985000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s12532-017-0124-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,4]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["124"],"URL":"https:\/\/doi.org\/10.1007\/s12532-017-0124-3","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"type":"print","value":"1867-2949"},{"type":"electronic","value":"1867-2957"}],"subject":[],"published":{"date-parts":[[2017,9,4]]}}}