{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T18:16:45Z","timestamp":1725733005340},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642390708"},{"type":"electronic","value":"9783642390715"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39071-5_28","type":"book-chapter","created":{"date-parts":[[2013,6,24]],"date-time":"2013-06-24T01:23:17Z","timestamp":1372036997000},"page":"377-393","source":"Crossref","is-referenced-by-count":1,"title":["Local Backbones"],"prefix":"10.1007","author":[{"given":"Ronald","family":"de Haan","sequence":"first","affiliation":[]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","volume":"43","author":"R. Aharoni","year":"1986","unstructured":"Aharoni, R., Linial, N.: Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas. J. Combin. Theory Ser. A\u00a043, 196\u2013204 (1986)","journal-title":"J. Combin. Theory Ser. A"},{"issue":"1\/2","key":"28_CR2","doi-asserted-by":"crossref","first-page":"123","DOI":"10.3233\/SAT190094","volume":"8","author":"A. Belov","year":"2012","unstructured":"Belov, A., Marques-Silva, J.: MUSer2: An efficient MUS extractor. J. on Satisfiability, Boolean Modeling and Computation\u00a08(1\/2), 123\u2013128 (2012)","journal-title":"J. on Satisfiability, Boolean Modeling and Computation"},{"key":"28_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/978-3-540-72788-0_29","volume-title":"Theory and Applications of Satisfiability Testing \u2013 SAT 2007","author":"J. Buresh-Oppenheim","year":"2007","unstructured":"Buresh-Oppenheim, J., Mitchell, D.: Minimum 2CNF resolution refutations in polynomial time. In: Marques-Silva, J., Sakallah, K.A. (eds.) SAT 2007. LNCS, vol.\u00a04501, pp. 300\u2013313. Springer, Heidelberg (2007)"},{"key":"28_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/11814948_6","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"J. Buresh-Oppenheim","year":"2006","unstructured":"Buresh-Oppenheim, J., Mitchell, D.: Minimum witnesses for unsatisfiable 2CNFs. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 42\u201347. Springer, Heidelberg (2006)"},{"key":"28_CR5","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A. Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A knowledge compilation map. J. Artif. Intell. Res.\u00a017, 229\u2013264 (2002)","journal-title":"J. Artif. Intell. Res."},{"issue":"3","key":"28_CR6","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"1","author":"W.F. Dowling","year":"1984","unstructured":"Dowling, W.F., Gallier, J.H.: Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Logic Programming\u00a01(3), 267\u2013284 (1984)","journal-title":"J. Logic Programming"},{"key":"28_CR7","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"28_CR8","unstructured":"Dubois, O., Dequen, G.: A backbone-search heuristic for efficient solving of hard 3-SAT formulae. In: Nebel, B. (ed.) Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, pp. 248\u2013253 (2001)"},{"issue":"1","key":"28_CR9","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science\u00a0410(1), 53\u201361 (2009)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"28_CR10","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/j.tcs.2005.10.005","volume":"351","author":"M.R. Fellows","year":"2006","unstructured":"Fellows, M.R., Szeider, S., Wrightson, G.: On finding short resolution refutations and small unsatisfiable subsets. Theoretical Computer Science\u00a0351(3), 351\u2013359 (2006)","journal-title":"Theoretical Computer Science"},{"key":"28_CR11","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol.\u00a0XIV. Springer, Berlin (2006)"},{"key":"28_CR12","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","volume":"42","author":"G. Gallo","year":"1993","unstructured":"Gallo, G., Longo, G., Pallotino, S., Nguyen, S.: Directed hypergraphs and applications. Discrete Applied Mathematics\u00a042, 177\u2013201 (1993)","journal-title":"Discrete Applied Mathematics"},{"key":"28_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/978-3-642-35843-2_20","volume-title":"SOFSEM 2013: Theory and Practice of Computer Science","author":"M. Gwynne","year":"2013","unstructured":"Gwynne, M., Kullmann, O.: Generalising and unifying SLUR and unit-refutation completeness. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds.) SOFSEM 2013. LNCS, vol.\u00a07741, pp. 220\u2013232. Springer, Heidelberg (2013)"},{"key":"28_CR14","unstructured":"Hertli, T., Moser, R.A., Scheder, D.: Improving PPSZ for 3-SAT using critical variables. In: Schwentick, T., D\u00fcrr, C. (eds.) Symposium on Theoretical Aspects of Computer Science, vol.\u00a09, pp. 237\u2013248. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2011)"},{"key":"28_CR15","unstructured":"Hoos, H.H., St\u00fctzle, T.: SATLIB: An online resource for research on SAT. In: Gent, I., van Maaren, H., Walsh, T. (eds.) SAT 2000: Highlights of Satisfiability Research in the year 2000. Frontiers in Artificial Intelligence and Applications, pp. 283\u2013292. Kluwer Academic (2000)"},{"issue":"4","key":"28_CR16","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. of Computer and System Sciences\u00a063(4), 512\u2013530 (2001)","journal-title":"J. of Computer and System Sciences"},{"key":"28_CR17","unstructured":"Kautz, H., Selman, B.: Pushing the envelope: planning, propositional logic, and stochastic search. In: Proceedings of the Thirteenth AAAI Conference on Artificial Intelligence, AAAI 1996, pp. 1194\u20131201. AAAI Press (1996)"},{"key":"28_CR18","unstructured":"Kilby, P., Slaney, J.K., Thi\u00e9baux, S., Walsh, T.: Backbones and backdoors in satisfiability. In: Proceedings of the Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference, AAAI 2005, Pittsburgh, Pennsylvania, USA, July 9-13, pp. 1368\u20131373 (2005)"},{"key":"28_CR19","unstructured":"Kullmann, O.: Investigating a general hierarchy of polynomially decidable classes of cnf\u2019s based on short tree-like resolution proofs. Electronic Colloquium on Computational Complexity (ECCC)\u00a06(41) (1999)"},{"key":"28_CR20","unstructured":"Kullmann, O.: An application of matroid theory to the SAT problem. In: Fifteenth Annual IEEE Conference on Computational Complexity, pp. 116\u2013124 (2000)"},{"key":"28_CR21","series-title":"Oxford Lecture Series in Mathematics and its","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its. Applications. Oxford University Press, Oxford (2006)"},{"key":"28_CR22","unstructured":"Parkes, A.J.: Clustering at the phase transition. In: Proceedings of the Fourteenth National Conference on Artificial Intelligence, AAAI 1997, pp. 340\u2013345. AAAI Press (1997)"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"Prelotani, D.: Efficiency and stability of hypergraph SAT algorithms. In: Johnson, D.S., Trick, M.A. (eds.) Cliques, Coloring and Satisfiability, pp. 479\u2013498. AMS (1996)","DOI":"10.1090\/dimacs\/026\/23"},{"key":"28_CR24","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0010-4655(96)00062-8","volume":"96","author":"J. Schneider","year":"1996","unstructured":"Schneider, J., Froschhammer, C., Morgenstern, I., Husslein, T., Singer, J.M.: Searching for backbones \u2013 an efficient parallel algorithm for the traveling salesman problem. Computer Physics Communications\u00a096, 173\u2013188 (1996)","journal-title":"Computer Physics Communications"},{"key":"28_CR25","unstructured":"Slaney, J.K., Walsh, T.: Backbones in optimization and approximation. In: Nebel, B. (ed.) Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI 2001, Seattle, Washington, USA, August 4-10, pp. 254\u2013259 (2001)"},{"key":"28_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"480","DOI":"10.1007\/10722167_36","volume-title":"Computer Aided Verification","author":"O. Strichman","year":"2000","unstructured":"Strichman, O.: Tuning SAT checkers for bounded model checking. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol.\u00a01855, pp. 480\u2013494. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39071-5_28","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T23:52:07Z","timestamp":1595980327000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39071-5_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642390708","9783642390715"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39071-5_28","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}