{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T14:39:17Z","timestamp":1777559957953,"version":"3.51.4"},"reference-count":23,"publisher":"SAGE Publications","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIC"],"published-print":{"date-parts":[[2018,5,17]]},"DOI":"10.3233\/aic-180763","type":"journal-article","created":{"date-parts":[[2018,4,20]],"date-time":"2018-04-20T10:56:48Z","timestamp":1524221808000},"page":"267-280","source":"Crossref","is-referenced-by-count":4,"title":["Towards backbone computing: A\u00a0Greedy-Whitening based approach"],"prefix":"10.1177","volume":"31","author":[{"given":"Yueling","family":"Zhang","sequence":"first","affiliation":[{"name":"National Research Center of Trustworthy Embedded Software, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Min","family":"Zhang","sequence":"additional","affiliation":[{"name":"National Research Center of Trustworthy Embedded Software, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Geguang","family":"Pu","sequence":"additional","affiliation":[{"name":"National Research Center of Trustworthy Embedded Software, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fu","family":"Song","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, ShanghaiTech University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianwen","family":"Li","sequence":"additional","affiliation":[{"name":"National Research Center of Trustworthy Embedded Software, East China Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/AIC-180763_ref1","unstructured":"A.\u00a0Belov and J.\u00a0Marques-Silva, Accelerating MUS extraction with recursive model rotation, in: Formal Methods in Computer-Aided Design (FMCAD), 2011."},{"key":"10.3233\/AIC-180763_ref2","doi-asserted-by":"crossref","unstructured":"G.\u00a0Carpaneto, M.\u00a0Dell\u2019Amico and P.\u00a0Toth, Exact solution of large-scale, asymmetric traveling salesman problems, ACM Transactions on Mathematical Software (TOMS) (1995).","DOI":"10.1145\/212066.212081"},{"key":"10.3233\/AIC-180763_ref3","unstructured":"S.\u00a0Climer and W.\u00a0Zhang, Searching for backbones and fat: A limit-crossing approach with applications, in: Proceedings of the Eighteenth National Conference on Artificial Intelligence (AAAI-02) \/Proceedings of the Fourteenth Innovative Applications of Artificial Intelligence Conference on Artificial Intelligence (IAAI-02), 2002."},{"key":"10.3233\/AIC-180763_ref4","doi-asserted-by":"crossref","unstructured":"J.\u00a0Culberson and I.P.\u00a0Gent, Frozen development in graph coloring, Theoretical Computer Science (2001).","DOI":"10.1016\/S0304-3975(01)00164-5"},{"key":"10.3233\/AIC-180763_ref5","unstructured":"O.\u00a0Dubois and G.\u00a0Dequen, A backbone-search heuristic for efficient solving of hard 3-SAT formulae, in: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01), 2001."},{"key":"10.3233\/AIC-180763_ref6","doi-asserted-by":"crossref","unstructured":"N.\u00a0E\u00e9n and N.\u00a0Sf\u00f6rensson, An extensible SAT-solver, in: International Conference on Theory and Applications of Satisfiability Testing, 2003.","DOI":"10.1007\/978-3-540-24605-3_37"},{"key":"10.3233\/AIC-180763_ref7","unstructured":"M.R.\u00a0Garey and D.S.\u00a0Johnson, A Guide to the Theory of NP-Completeness, WH Freemann, New York, 1979."},{"key":"10.3233\/AIC-180763_ref8","unstructured":"I.P.\u00a0Gent and T.\u00a0Walsh, The SAT phase transition, in: Proceedings of European Association for Artificial Intelligence (ECAI), 1994."},{"key":"10.3233\/AIC-180763_ref11","unstructured":"M.\u00a0Janota, I.\u00a0Lynce and J.\u00a0Marques-Silva, Experimental analysis of backbone computation algorithms, in: International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA), 2012."},{"key":"10.3233\/AIC-180763_ref12","doi-asserted-by":"crossref","unstructured":"M.\u00a0Janota, I.\u00a0Lynce and J.\u00a0Marques-Silva, Algorithms for computing backbones of propositional formulae, AI Communications (2015).","DOI":"10.3233\/AIC-140640"},{"key":"10.3233\/AIC-180763_ref14","unstructured":"P.\u00a0Kilby, J.\u00a0Slaney and T.\u00a0Walsh, The backbone of the travelling salesperson, in: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05), 2005."},{"key":"10.3233\/AIC-180763_ref15","doi-asserted-by":"crossref","unstructured":"J.\u00a0Marques-Silva, M.\u00a0Janota and I.\u00a0Lynce, On computing backbones of propositional theories, in: Proceedings of European Association for Artificial Intelligence (ECAI), 2010.","DOI":"10.3233\/978-1-60750-606-5-15"},{"key":"10.3233\/AIC-180763_ref16","doi-asserted-by":"crossref","unstructured":"J.\u00a0Marques-Silva and I.\u00a0Lynce, On improving MUS extraction algorithms, in: International Conference on Theory and Applications of Satisfiability Testing, 2011.","DOI":"10.1007\/978-3-642-21581-0_14"},{"key":"10.3233\/AIC-180763_ref17","unstructured":"M.E.B.\u00a0Mena\u0131, A two-phase backbone-based search heuristic for partial MAX-SAT\u00a0\u2013 An initial investigation, in: International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, 2005."},{"key":"10.3233\/AIC-180763_ref18","doi-asserted-by":"crossref","unstructured":"M.E.B.\u00a0Mena\u0131, A backbone-based co-evolutionary heuristic for partial MAX-SAT, in: International Conference on Artificial Evolution (Evolution Artificielle), 2005.","DOI":"10.1007\/11740698_14"},{"key":"10.3233\/AIC-180763_ref19","unstructured":"C.\u00a0Menc\u0131a, A.\u00a0Previti and J.\u00a0Marques-Silva, Literal-based MCS extraction, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-15), 2015."},{"key":"10.3233\/AIC-180763_ref20","doi-asserted-by":"crossref","unstructured":"R.\u00a0Monasson, R.\u00a0Zecchina, S.\u00a0Kirkpatrick, B.\u00a0Selman and L.\u00a0Troyansky, Determining computational complexity from characteristic phase transitions, Nature (1999).","DOI":"10.1038\/22055"},{"key":"10.3233\/AIC-180763_ref22","unstructured":"B.\u00a0Selman, H.\u00a0Kautz and B.\u00a0Cohen, Local search strategies for satisfiability testing, in: Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 1993."},{"key":"10.3233\/AIC-180763_ref23","unstructured":"T.\u00a0Walsh and J.\u00a0Slaney, Backbones in optimization and approximation, in: Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01), 2001."},{"key":"10.3233\/AIC-180763_ref24","unstructured":"W.\u00a0Zhang and M.\u00a0Looks, A novel local search algorithm for the traveling salesman problem that exploits backbones, in: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-05), 2005."},{"key":"10.3233\/AIC-180763_ref25","unstructured":"W.\u00a0Zhang, A.\u00a0Rangan and M.\u00a0Looks, Backbone guided local search for maximum satisfiability, in: Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI-03), 2003."},{"key":"10.3233\/AIC-180763_ref26","unstructured":"C.S.\u00a0Zhu, G.\u00a0Weissenbacher and S.\u00a0Malik, Post-silicon fault localisation using maximum satisfiability and backbones, in: International Conference on Formal Methods in Computer-Aided Design, 2011."},{"key":"10.3233\/AIC-180763_ref27","doi-asserted-by":"crossref","unstructured":"C.S.\u00a0Zhu, G.\u00a0Weissenbacher, D.\u00a0Sethi and S.\u00a0Malik, SAT-based techniques for determining backbones for post-silicon fault localisation, in: IEEE International High Level Design Validation and Test Workshop, 2011.","DOI":"10.1109\/HLDVT.2011.6113981"}],"container-title":["AI Communications"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/AIC-180763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T18:27:47Z","timestamp":1777400867000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/AIC-180763"}},"subtitle":[],"editor":[{"given":"Pascal","family":"Fontaine","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Cezary","family":"Kaliszyk","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Stephan","family":"Schulz","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Josef","family":"Urban","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2018,5,17]]},"references-count":23,"journal-issue":{"issue":"3"},"URL":"https:\/\/doi.org\/10.3233\/aic-180763","relation":{},"ISSN":["1875-8452","0921-7126"],"issn-type":[{"value":"1875-8452","type":"electronic"},{"value":"0921-7126","type":"print"}],"subject":[],"published":{"date-parts":[[2018,5,17]]}}}