{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T02:17:13Z","timestamp":1773886633911,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642114397","type":"print"},{"value":"9783642114403","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11440-3_18","type":"book-chapter","created":{"date-parts":[[2010,2,2]],"date-time":"2010-02-02T16:03:36Z","timestamp":1265126616000},"page":"191-203","source":"Crossref","is-referenced-by-count":94,"title":["A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique"],"prefix":"10.1007","author":[{"given":"Etsuji","family":"Tomita","sequence":"first","affiliation":[]},{"given":"Yoichi","family":"Sutani","sequence":"additional","affiliation":[]},{"given":"Takanori","family":"Higashi","sequence":"additional","affiliation":[]},{"given":"Shinya","family":"Takahashi","sequence":"additional","affiliation":[]},{"given":"Mitsuo","family":"Wakatsuki","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1142\/S0219720006001680","volume":"4","author":"D.K.C. Bahadur","year":"2006","unstructured":"Bahadur, D.K.C., Tomita, E., Suzuki, J., Horimoto, K., Akutsu, T.: Protein threading with profiles and distance constraints using clique based algorithms. J. Bioinformatics and Computational Biology\u00a04, 19\u201342 (2006)","journal-title":"J. Bioinformatics and Computational Biology"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"Balas, E., Ceria, S., Cornu\u00e9jols, G., Pataki, G.: Polyhedral methods for the maximum clique problem. In: Johnson, Trick (eds.) [13], pp. 11\u201328 (1996)","DOI":"10.1090\/dimacs\/026\/02"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Bomze, I.M., Budinich, M., Pardalos, P.M., Pelillo, M.: The maximum clique problem. In: Du, D.-Z., Pardalos, P.M. (eds.) Handbook of Combinatorial Optimization, Supplement vol.\u00a0A, pp. 1\u201374 (1999)","DOI":"10.1007\/978-1-4757-3023-4_1"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"Bourjolly, J.-M., Gill, P., Laporte, G., Mercure, H.: An exact quadratic 0-1 algorithm for the stable set problem. In: Johnson, Trick (eds.) [13], pp. 53\u201373 (1996)","DOI":"10.1090\/dimacs\/026\/04"},{"key":"18_CR5","first-page":"3","volume":"17","author":"J.B. Brown","year":"2006","unstructured":"Brown, J.B., Bahadur, D.K.C., Tomita, E., Akutsu, T.: Multiple methods for protein side chain packing using maximum weight cliques. Genome Inform.\u00a017, 3\u201312 (2006)","journal-title":"Genome Inform."},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2005.05.026","volume":"173","author":"S. Butenko","year":"2006","unstructured":"Butenko, S., Wilhelm, W.E.: Clique-detection models in computational biochemistry and genomics - invited review -. European J. Operational Research\u00a0173, 1\u201317 (2006)","journal-title":"European J. Operational Research"},{"key":"18_CR7","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","volume":"9","author":"R. Carraghan","year":"1990","unstructured":"Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Operations Research Letters\u00a09, 375\u2013382 (1990)","journal-title":"Operations Research Letters"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/3-540-45749-6_44","volume-title":"Algorithms - ESA 2002","author":"T. Fahle","year":"2002","unstructured":"Fahle, T.: Simple and fast: Improving a branch-and-bound algorithm for maximum clique. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 485\u2013498. Springer, Heidelberg (2002)"},{"key":"18_CR9","unstructured":"Fujii, T., Tomita, E.: On efficient algorithms for finding a maximum clique. Technical Report of IECE, AL81-113, pp. 25\u201334 (1982)"},{"key":"18_CR10","unstructured":"Higashi, T., Tomita, E.: A more efficient algorithm for finding a maximum clique based on an improved approximate coloring. Technical Report of Univ. Electro-Commun, UEC-TR-CAS5-2006 (2006)"},{"key":"18_CR11","doi-asserted-by":"publisher","first-page":"2787","DOI":"10.1016\/j.cor.2005.01.011","volume":"33","author":"W.J. Hoeve van","year":"2006","unstructured":"van Hoeve, W.J.: Exploiting semidefinite relaxations in costraint programming. Computers & Operations Research\u00a033, 2787\u20132804 (2006)","journal-title":"Computers & Operations Research"},{"key":"18_CR12","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Johnson, D.S., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability. DIMACS Series in Discr. Math. and Theoret. Comput. Sci., vol.\u00a026 (1996)","DOI":"10.1090\/dimacs\/026"},{"key":"18_CR14","unstructured":"http:\/\/www.cs.sunysb.edu\/~algorith\/implement\/dimacs\/distrib\/color\/graph\/form"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"Matsunaga, T., Yonemori, C., Tomita, E., Muramatsu, M.: Clique-based data mining for related genes in a biomedical database. BMC Bioinformatics\u00a010 (2009)","DOI":"10.1186\/1471-2105-10-205"},{"key":"18_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(01)00290-6","volume":"120","author":"P.R.J. \u00d6sterg\u00e5rd","year":"2002","unstructured":"\u00d6sterg\u00e5rd, P.R.J.: A fast algorithm for the maximum clique problem. Discrete Applied Math.\u00a0120, 197\u2013207 (2002)","journal-title":"Discrete Applied Math."},{"key":"18_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1007\/978-3-540-45193-8_43","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2003","author":"J.C. R\u00e9gin","year":"2003","unstructured":"R\u00e9gin, J.C.: Using constraint programming to solve the maximum clique problem. In: Rossi, F. (ed.) CP 2003. LNCS, vol.\u00a02833, pp. 634\u2013648. Springer, Heidelberg (2003)"},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1287\/ijoc.10.4.438","volume":"10","author":"E.C. Sewell","year":"1998","unstructured":"Sewell, E.C.: A branch and bound algorithm for the stability number of a sparse graph. INFORMS J. Computing\u00a010, 438\u2013447 (1998)","journal-title":"INFORMS J. Computing"},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/scj.4690210301","volume":"21","author":"M. Shindo","year":"1990","unstructured":"Shindo, M., Tomita, E.: A simple algorithm for finding a maximum clique and its worst-case time complexity. Systems and Computers in Japan\u00a021, 1\u201313 (1990)","journal-title":"Systems and Computers in Japan"},{"key":"18_CR20","unstructured":"Shindo, M., Tomita, E., Maruyama, Y.: An efficient algorithm for finding a maximum clique. Technical Report of IEC, CAS86-5, pp. 33\u201340 (1986)"},{"key":"18_CR21","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1023\/A:1023245011830","volume":"26","author":"V. Stix","year":"2003","unstructured":"Stix, V.: Target-oriented branch and bound method for global optimization. J. Global Optim.\u00a026, 261\u2013277 (2003)","journal-title":"J. Global Optim."},{"key":"18_CR22","unstructured":"Sutani, Y., Tomita, E.: Computational experiments and analyses of a more efficient algorithm for finding a maximum clique. Technical Report of IPSJ, 2005-MPS-57, pp. 45\u201348 (2005)"},{"key":"18_CR23","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s10898-006-9039-7","volume":"37","author":"E. Tomita","year":"2009","unstructured":"Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Global Optim.\u00a037, 95\u2013111 (2009); J. Global Optim. 37, 95\u2013311 (2007)","journal-title":"J. Global Optim."},{"key":"18_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/3-540-45066-1_22","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"E. Tomita","year":"2003","unstructured":"Tomita, E., Seki, T.: An efficient branch-and-bound algorithm for finding a maximum clique. In: Calude, C.S., Dinneen, M.J., Vajnovszki, V. (eds.) DMTCS 2003. LNCS, vol.\u00a02731, pp. 278\u2013289. Springer, Heidelberg (2003)"},{"key":"#cr-split#-18_CR25.1","doi-asserted-by":"crossref","unstructured":"Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments (An invited paper in the Special Issue on COCOON 2004). Theoret. Comput. Sci.\u00a0363, 28\u201342 (2006);","DOI":"10.1016\/j.tcs.2006.06.015"},{"key":"#cr-split#-18_CR25.2","doi-asserted-by":"crossref","unstructured":"The preliminary version appeared in Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques. In: Chwa, K.-Y., Munro, J.I.J. (eds.) COCOON 2004. LNCS, vol.\u00a03106, pp. 161\u2013170. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-27798-9_19"},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0167-6377(97)00054-0","volume":"21","author":"D.R. Wood","year":"1997","unstructured":"Wood, D.R.: An algorithm for finding a maximum clique in a graph. Operations Research Letters\u00a021, 211\u2013217 (1997)","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11440-3_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:40:32Z","timestamp":1606185632000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11440-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114397","9783642114403"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11440-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}