{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:28:17Z","timestamp":1742394497104},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2008,5,1]],"date-time":"2008-05-01T00:00:00Z","timestamp":1209600000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sci. China Ser. F-Inf. Sci."],"published-print":{"date-parts":[[2008,5]]},"DOI":"10.1007\/s11432-008-0042-0","type":"journal-article","created":{"date-parts":[[2008,5,10]],"date-time":"2008-05-10T10:05:56Z","timestamp":1210413956000},"page":"476-488","source":"Crossref","is-referenced-by-count":7,"title":["Backbone analysis and algorithm design for the quadratic assignment problem"],"prefix":"10.1007","volume":"51","author":[{"given":"He","family":"Jiang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"XianChao","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GuoLiang","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MingChu","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,5,11]]},"reference":[{"key":"42_CR1","first-page":"10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: W. H. Freeman, 1979. 10\u201335"},{"issue":"3","key":"42_CR2","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni S, Gonzalez T. P-complete approximation problems. J ACM, 1976, 23(3): 555\u2013565","journal-title":"J ACM"},{"key":"42_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-6089-0","volume-title":"Tabu Search","author":"F. Glover","year":"1997","unstructured":"Glover F, Laguna M. Tabu Search. Boston: Kluwer Academic Publishers, 1997"},{"key":"42_CR4","first-page":"11","volume-title":"New Ideas in Optimization","author":"M. Dorigo","year":"1999","unstructured":"Dorigo M, DiCaro G. The ant colony optimization meta-heuristic. In: Corne D, Dorigo M, Glover F, eds. New Ideas in Optimization. London: McGraw Hill, UK, 1999. 11\u201332"},{"key":"42_CR5","volume-title":"Ant Colony Algorithms: Theory and Applications (in Chinese)","author":"H. B. Duan","year":"2005","unstructured":"Duan H B. Ant Colony Algorithms: Theory and Applications (in Chinese). Beijing: Science Press, 2005"},{"key":"42_CR6","volume-title":"Genetic Algorithm and its Application (in Chinese)","author":"G. L. Chen","year":"1996","unstructured":"Chen G L, Wang X F, Zhuang Z Q. Genetic Algorithm and its Application (in Chinese). Beijing: Posts & Telecom Press, 1996"},{"key":"42_CR7","volume-title":"Non numeric Parallel Algorithms: Simulated Annealing (in Chinese)","author":"L. S. Kang","year":"1994","unstructured":"Kang L S, Xie Y, You S Y, et al. Non numeric Parallel Algorithms: Simulated Annealing (in Chinese). Beijing: Science Press, 1994"},{"key":"42_CR8","volume-title":"Neutral Networks and Applications (in Chinese)","author":"Z. H. Zhou","year":"2004","unstructured":"Zhou Z H, Cao C G. Neutral Networks and Applications (in Chinese). Beijing: Press of Tsinghua University, 2004"},{"key":"42_CR9","volume-title":"Introduction to Modern Computational Theory: Background, Perspective, and Algorithms Research of NP-hard Problems (in Chinese)","author":"W. Q. Huang","year":"2004","unstructured":"Huang W Q, Xu R C. Introduction to Modern Computational Theory: Background, Perspective, and Algorithms Research of NP-hard Problems (in Chinese). Beijing: Science Press, 2004"},{"key":"42_CR10","first-page":"254","volume-title":"Proc 17th Intern Joint Conf Artif Intell (IJCAI-01)","author":"J. Slaney","year":"2001","unstructured":"Slaney J, Walsh T. Backbones in optimization and approximation. In: Proc 17th Intern Joint Conf Artif Intell (IJCAI-01). San Francisco: Morgan Kaufmann Publishers, 2001. 254\u2013259"},{"issue":"8","key":"42_CR11","first-page":"133","volume":"400","author":"R. Monasson","year":"1998","unstructured":"Monasson R, Zecchina R, Kirkpatrick S, et al. Determining computational complexity for characteristic \u2018phase transition\u2019. Nature, 1998, 400(8): 133\u2013137","journal-title":"Nature"},{"issue":"1","key":"42_CR12","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1613\/jair.1389","volume":"21","author":"W. X. Zhang","year":"2004","unstructured":"Zhang W X. Phase transition and backbones of the asymmetric traveling salesman problem. J Artif Intell Res, 2004, 21(1): 471\u2013497","journal-title":"J Artif Intell Res"},{"issue":"1","key":"42_CR13","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0167-739X(02)00106-1","volume":"19","author":"J. Schneider","year":"2003","unstructured":"Schneider J. Searching for backbones-a high-performance parallel algorithm for solving combinatorial optimization problems. Future Gener Comput Syst, 2003, 19(1): 121\u2013131","journal-title":"Future Gener Comput Syst"},{"issue":"1","key":"42_CR14","first-page":"35","volume":"14","author":"P. Zou","year":"2003","unstructured":"Zou P, Zhou Z, Chen G L, et al. A multilevel reduction algorithm to TSP. J Software (in Chinese), 2003, 14(1): 35\u201342","journal-title":"J Software (in Chinese)"},{"key":"42_CR15","first-page":"343","volume-title":"Proc 19th Intern Joint Conf Artif Intell (IJCAI-05)","author":"W. X. Zhang","year":"2005","unstructured":"Zhang W X, Looks M. A novel local search algorithm for the traveling salesman problem that exploit backbones. In: Proc 19th Intern Joint Conf Artif Intell (IJCAI-05), San Francisco: Morgan Kaufmann Publishers, 2005. 343\u2013351"},{"issue":"1","key":"42_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.artint.2004.04.001","volume":"158","author":"W. X. Zhang","year":"2004","unstructured":"Zhang W X. Configuration landscape analysis and backbone guided local search: Part I: Satisifiability and maximum satisfiability. Artif Intell, 2004, 158(1): 1\u201326","journal-title":"Artif Intell"},{"key":"42_CR17","first-page":"248","volume-title":"Proc 17th Intern Joint Conf Artif Intell (IJCAI-01)","author":"O. Dubois","year":"2001","unstructured":"Dubois O, Seymour P. A backbone-search heuristic for efficient solving of hard 3-SAT formula. In: Proc 17th Intern Joint Conf Artif Intell (IJCAI-01). San Francisco: Morgan Kaufmann Publishers, 2001. 248\u2013253"},{"key":"42_CR18","first-page":"100","volume-title":"Proc 9th Intern Symposium on Artif Intell Math (AI & Math-06)","author":"F. J. Valnir","year":"2006","unstructured":"Valnir F J. Backbone guided dynamic local search for propositional satisfiability. In: Proc 9th Intern Symposium on Artif Intell Math (AI & Math-06). New York: Springer, 2006. 100\u2013108"},{"issue":"10","key":"42_CR19","doi-asserted-by":"crossref","first-page":"1691","DOI":"10.1360\/jos161691","volume":"16","author":"P. Zou","year":"2005","unstructured":"Zou P, Zhou Z, Chen G L, et al. Approximate-backbone guided fast ant algorithms to QAP. J Software, 2005, 16(10): 1691\u20131698","journal-title":"J Software"},{"key":"42_CR20","first-page":"175","volume-title":"Proc 19th Intern Joint Conf Artif Intell (IJCAI05)","author":"P. Kilby","year":"2005","unstructured":"Kilby P, Slaney J, Walsh T. The backbone of the traveling salesperson. In: Proc 19th Intern Joint Conf Artif Intell (IJCAI05). San Francisco: Morgan Kaufmann Publishers, 2005, 175\u2013181"},{"key":"42_CR21","unstructured":"Taillard E D. Fant: fast ant system. Techn Report IDSIA-46-98, 1998"},{"issue":"1","key":"42_CR22","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0377-2217(91)90197-4","volume":"55","author":"R. E. Burkard","year":"1991","unstructured":"Burkard R E, Karisch S, Rendl F. Qaplib: a quadratic assignment problem library. Eur J Oper Res, 1991, 55(1): 115\u2013119","journal-title":"Eur J Oper Res"},{"issue":"2","key":"42_CR23","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1057\/palgrave.jors.2600676","volume":"50","author":"L. Gambardella","year":"1999","unstructured":"Gambardella L, Taillard\u2019 E, Dorigo M. Ant colonies for the QAP. J Oper Res Soc, 1999, 50(2): 167\u2013176","journal-title":"J Oper Res Soc"},{"issue":"3","key":"42_CR24","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1023\/A:1015057701750","volume":"8","author":"M. Middendorf","year":"2002","unstructured":"Middendorf M, Reischle F, Schmeck H. Multi colony ant algorithms. J Heuristics, 2002, 8(3): 305\u2013320","journal-title":"J Heuristics"},{"issue":"3","key":"42_CR25","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1287\/ijoc.15.3.320.16076","volume":"15","author":"Z. Drezner","year":"2003","unstructured":"Drezner Z. A new genetic algorithm for the quadratic assignment problem. Informs J Comput, 2003, 15(3): 320\u2013330","journal-title":"Informs J Comput"},{"issue":"3","key":"42_CR26","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0167-2789(00)00196-2","volume":"149","author":"K. Tsuchiya","year":"2001","unstructured":"Tsuchiya K, Nishiyama T, Tsujita K. A deterministic annealing algorithm for a combinatorial optimization problem using replicator equations. Phys D: Nonlin Phenom, 2001, 149(3): 161\u2013173","journal-title":"Phys D: Nonlin Phenom"},{"issue":"1\u20134","key":"42_CR27","first-page":"239","volume":"43","author":"S. Ishii","year":"2001","unstructured":"Ishii S, Sato M. Doubly constrained network for combinatorial optimization. Neurocomputing, 2001, 43(1\u20134): 239\u2013257","journal-title":"Neurocomputing"},{"issue":"27","key":"42_CR28","first-page":"12","volume":"2","author":"A. Misevicius","year":"2003","unstructured":"Misevicius A. A modification of tabu search and its applications to the quadratic assignment problem. Inform Techn Control, 2003, 2(27): 12\u201320","journal-title":"Inform Techn Control"},{"issue":"2","key":"42_CR29","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1016\/S0377-2217(03)00438-7","volume":"160","author":"Z. Drezner","year":"2005","unstructured":"Drezner Z. The extended concentric tabu for the quadratic assignment problem. Eur J Oper Res, 2005, 160(2): 416\u2013422","journal-title":"Eur J Oper Res"},{"key":"42_CR30","first-page":"571","volume-title":"Proc 5th Metaheuristics Intern Conf (MIC2003)","author":"C. A. S. Oliveira","year":"2003","unstructured":"Oliveira C A S, Pardalos P M, Resende M G C. Grasp with path-relinking for the QAP. In: Proc 5th Metaheuristics Intern Conf (MIC2003). Boston: Kluwer Academic Publishers, 2003. 571\u2013576"},{"key":"42_CR31","unstructured":"Boese K D. Cost versus distance in the traveling salesman problem. Tech Report CSD-950018, 1995"},{"issue":"1","key":"42_CR32","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1162\/106365600568103","volume":"8","author":"P. Merz","year":"2000","unstructured":"Merz P, Freisleben B. Fitness landscapes and memetic algorithms and greedy operators for graph bi-partitioning. Evolut Comput, 2000, 8(1): 61\u201391","journal-title":"Evolut Comput"},{"issue":"1","key":"42_CR33","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1023\/A:1018983524911","volume":"86","author":"C. R. Reeves","year":"1999","unstructured":"Reeves C R. Landscapes, operators and heuristic search. Annals Oper Res, 1999, 86(1): 473\u2013490","journal-title":"Annals Oper Res"},{"key":"42_CR34","first-page":"2063","volume-title":"Proc IEEE Congress on Evolut Computation (CEC\u201999)","author":"P. Merz","year":"1999","unstructured":"Merz P, Freisleben B. A comparison of memetic algorithms, tabu search, and ant colonies for the quadratic assignment problem. In: Proc IEEE Congress on Evolut Computation (CEC\u201999). Piscataway: IEEE Press, 1999. 2063\u20132070"}],"container-title":["Science in China Series F: Information Sciences"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-008-0042-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11432-008-0042-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11432-008-0042-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T15:35:55Z","timestamp":1559403355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11432-008-0042-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5]]},"references-count":34,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["42"],"URL":"https:\/\/doi.org\/10.1007\/s11432-008-0042-0","relation":{},"ISSN":["1009-2757","1862-2836"],"issn-type":[{"value":"1009-2757","type":"print"},{"value":"1862-2836","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5]]}}}