{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T23:15:51Z","timestamp":1776122151983,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642131929","type":"print"},{"value":"9783642131936","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13193-6_2","type":"book-chapter","created":{"date-parts":[[2010,4,27]],"date-time":"2010-04-27T11:54:59Z","timestamp":1272369299000},"page":"13-22","source":"Crossref","is-referenced-by-count":11,"title":["Computational Challenges with Cliques, Quasi-cliques and Clique Partitions in Graphs"],"prefix":"10.1007","author":[{"given":"Panos M.","family":"Pardalos","sequence":"first","affiliation":[]},{"given":"Steffen","family":"Rebennack","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","series-title":"Electronic Edition 2000","doi-asserted-by":"publisher","DOI":"10.1007\/b100033","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory. Electronic Edition 2000. Springer, New York (2000)"},{"key":"2_CR2","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"2000","unstructured":"West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice-Hall, Englewood Cliffs (2000)","edition":"2"},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Proceedings of a Symposium on the Complexity of Computer Computations","author":"R. Karp","year":"1972","unstructured":"Karp, R.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"2_CR4","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, A guide to the Theory of NP-Completeness. In: Klee, V. (ed.) A series of books in the mathematical sciences. W. H. Freeman and Company, New York (1979)"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/SFCS.1992.267824","volume-title":"Proceedings 33rd IEEE Symposium on Foundations of Computer Science","author":"S. Arora","year":"1992","unstructured":"Arora, S., Safra, S.: Probabilistic Checking of Proofs; a new Characterization of NP. In: Proceedings 33rd IEEE Symposium on Foundations of Computer Science, pp. 2\u201313. IEEE Computer Society, Los Angeles (1992)"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problmes. JACM\u00a041, 960\u2013981 (1994)","journal-title":"JACM"},{"key":"2_CR7","first-page":"1","volume-title":"Handbook of Combinatorial Optimization","author":"I. Bomze","year":"1999","unstructured":"Bomze, I., Budinich, M., Pardalos, P., Pelillo, M.: The maximum clique problem. In: Du, D.Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, pp. 1\u201374. Kluwer Academic Publishers, Dordrecht (1999)"},{"key":"2_CR8","doi-asserted-by":"crossref","first-page":"3676","DOI":"10.1007\/978-0-387-74759-0_634","volume-title":"Encyclopedia of Optimization","author":"S. Rebennack","year":"2008","unstructured":"Rebennack, S.: Stable Set Problem: Branch & Cut Algorithms. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, 2nd edn., pp. 3676\u20133688. Springer, Heidelberg (2008)","edition":"2"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Rebennack, S., Oswald, M., Theis, D., Seitz, H., Reinelt, G., Pardalos, P.: A Branch and Cut solver for the maximum stable set problem. Journal of Combinatorial Optimization, doi:10.1007\/s10878-009-9264-3","DOI":"10.1007\/s10878-009-9264-3"},{"key":"2_CR10","first-page":"331","volume-title":"Handbook of Combinatorial Optimization","author":"P. Pardalos","year":"1990","unstructured":"Pardalos, P., Mavridou, T., Xue, J.: The graph coloring problem: a bibliographic survey. In: Du, D.Z., Pardalos, P. (eds.) Handbook of Combinatorial Optimization, vol.\u00a02, pp. 331\u2013395. Kluwer Academic Publishers, Dordrecht (1990)"},{"key":"2_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-92695-5_4","volume-title":"Learning and Intelligent Optimization","author":"M. Brunato","year":"2008","unstructured":"Brunato, M., Hoos, H., Battiti, R.: On Effectively Finding Maximal Quasi-cliques in Graphs. In: Maniezzo, V., Battiti, R., Watson, J.-P. (eds.) LION 2007 II. LNCS, vol.\u00a05313, pp. 41\u201355. Springer, Heidelberg (2008)"},{"issue":"1","key":"2_CR12","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1511\/2000.1.9","volume":"88","author":"B. Hayes","year":"2000","unstructured":"Hayes, B.: Graph Theory in Practice: Part I. American Scientist\u00a088(1), 9 (2000)","journal-title":"American Scientist"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Cipra, B.: Massive graphs pose big problems. Technical report, SIAM NEWS, April 22 (1999)","DOI":"10.1145\/337885.337889"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/3-540-45995-2_51","volume-title":"LATIN 2002: Theoretical Informatics","author":"J. Abello","year":"2002","unstructured":"Abello, J., Resende, M., Sudarsky, S.: Massive Quasi-Clique Detection. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, p. 598. Springer, Heidelberg (2002)"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1007\/978-3-642-04174-7_57","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"Q. Ye","year":"2009","unstructured":"Ye, Q., Wu, B., Suo, L., Zhu, T., Han, C., Wang, B.: TeleComVis: Exploring Temporal Communities in Telecom Networks. In: Buntine, W., Grobelnik, M., Mladeni\u0107, D., Shawe-Taylor, J. (eds.) ECML PKDD 2009. LNCS, vol.\u00a05782, pp. 755\u2013758. Springer, Heidelberg (2009)"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Abello, J., Pardalos, P., Resende, M.: On Maximum Clique Problems in Very Lagre Graphs. In: External Memory Algorithms. DIMACS Series, pp. 119\u2013130. American Mathematical Society, Providence (1999)","DOI":"10.1090\/dimacs\/050\/06"},{"issue":"5","key":"2_CR17","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1109\/TKDE.2007.190733","volume":"20","author":"A. Nanavati","year":"2008","unstructured":"Nanavati, A., Singh, R., Chakraborty, D., Dasgupta, K., Mukherjea, S., Das, G., Gurumurthy, S., Joshi, A.: Analyzing the Structure and Evolution of Massive Telecom Graphs. IEEE Transactions on Knowledge and Data Engineering\u00a020(5), 703\u2013718 (2008)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"2_CR18","unstructured":"Narasimhamurthy, A., Greene, D., Hurley, N., Cunningham, P.: Community Finding in Large Social Networks Through Problem Decomposition. Technical report, UCD School of Computer Science and Informatics (2008)"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On Power-law Relationships of the Internet Topology. In: Proceedings of the ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 251\u2013262 (1999)","DOI":"10.1145\/316188.316229"},{"issue":"5","key":"2_CR20","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1511\/2006.61.3495","volume":"94","author":"B. Hayes","year":"2006","unstructured":"Hayes, B.: Connecting the Dots: Can the tools of graph theory and social-network studies unravel the next big plot? American Scientist\u00a094(5), 400 (2006)","journal-title":"American Scientist"},{"key":"2_CR21","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-28550-4_11","volume-title":"Methods and Models in Transport and Telecommunications","author":"L. Schintler","year":"2005","unstructured":"Schintler, L., Gorman, S., Reggiani, A., Patuelli, R., Nijkamp, P.: Small-World Phenomena in Communications Networks: A Cross-Atlantic Comparison. Advances in Spatial Science. In: Methods and Models in Transport and Telecommunications, pp. 201\u2013220. Springer, Heidelberg (2005)"},{"key":"2_CR22","volume-title":"Clustering Challenges in Biological Networks","year":"2009","unstructured":"Butenko, S., Chaovalitwongse, W., Pardalos, P. (eds.): Clustering Challenges in Biological Networks. World Scientific, Singapore (2009)"},{"key":"2_CR23","series-title":"Springer Optimization and Its Applications","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-0-387-98096-6_12","volume-title":"Optimization: Structure and Applications","author":"S. Butenko","year":"2009","unstructured":"Butenko, S., Pardalos, P., Sergieko, I., Shylo, V., Stetsyuk, P.: Estimating the size of correcting codes using extremal graph problems. In: Optimization: Structure and Applications. Springer Optimization and Its Applications, vol.\u00a032, pp. 227\u2013243. Springer, Heidelberg (2009)"},{"key":"2_CR24","doi-asserted-by":"publisher","first-page":"1324","DOI":"10.1109\/18.45293","volume":"35","author":"C. Pul van","year":"1989","unstructured":"van Pul, C., Etzion, T.: New lower bounds for constatn weight codes. IEEE Trans. Inform. Theory\u00a035, 1324\u20131329 (1989)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"2_CR25","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0966-8349(97)00015-6","volume":"5","author":"M. Gendreau","year":"1997","unstructured":"Gendreau, M., Laporte, G., Semet, F.: Solving an ambulance location model by tabu search. Location Science\u00a05, 75\u201388 (1997)","journal-title":"Location Science"},{"key":"2_CR26","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/S0305-0548(99)00088-X","volume":"29","author":"L. Brotcorne","year":"2002","unstructured":"Brotcorne, L., Laporte, G., Semet, F.: Fast heuristics for large scale covering ocation problems. Computers and Operations Research\u00a029, 651\u2013665 (2002)","journal-title":"Computers and Operations Research"},{"key":"2_CR27","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0022-2836(90)90312-A","volume":"212","author":"E. Mitchell","year":"1990","unstructured":"Mitchell, E., Artymiuk, P., Rice, D., Willett, P.: Use of techniques derived from graph theory to compare secondary structure motifs in proteins. J. Mol. Biol.\u00a0212, 151 (1990)","journal-title":"J. Mol. Biol."},{"key":"2_CR28","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1021\/ci00056a002","volume":"27","author":"A. Brint","year":"1987","unstructured":"Brint, A., Willett, P.: Algorithms for the Identification of Three-Dimensional Maximal Common Substructures. J. Chem. ZnJ Comput. Sci.\u00a027, 152\u2013158 (1987)","journal-title":"J. Chem. ZnJ Comput. Sci."},{"key":"2_CR29","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S1093-3263(97)00089-2","volume":"15","author":"E. Gardiner","year":"1997","unstructured":"Gardiner, E., Artymiuk, P., Willett, P.: Clique-detection algorithms for matching three-dimensional molecular structures. Journal of Molecular Graphics and Modelling\u00a015, 245\u2013253 (1997)","journal-title":"Journal of Molecular Graphics and Modelling"},{"key":"2_CR30","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1023\/A:1021271615909","volume":"16","author":"J. Raymond","year":"2002","unstructured":"Raymond, J., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of Computer-Aided Molecular Design\u00a016, 521\u2013533 (2002)","journal-title":"Journal of Computer-Aided Molecular Design"},{"key":"2_CR31","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1021\/ci990262o","volume":"40","author":"E. Gardiner","year":"2000","unstructured":"Gardiner, E., Willett, P., Artymiuk, P.: Graph-theoretic techniques for macromolecular docking. J. Chem. Inf. Comput.\u00a040, 273\u2013279 (2000)","journal-title":"J. Chem. Inf. Comput."},{"key":"2_CR32","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.: Clique-detection models in computational biochemistry and genomics. Euorpean Journal of Operational Research\u00a0173, 1\u201317 (2006)","journal-title":"Euorpean Journal of Operational Research"},{"key":"2_CR33","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1515\/crll.1930.163.231","volume":"163","author":"O. Keller","year":"1930","unstructured":"Keller, O.: \u00dcber die l\u00fcckenlose Einf\u00fcllung des Raumes mit W\u00fcrfeln. J. Reine Angew. Math.\u00a0163, 231\u2013248 (1930)","journal-title":"J. Reine Angew. Math."},{"key":"2_CR34","unstructured":"Minkowski, H.: Diophantische Approximationen. Teubner, Leipzig"},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"Stein, S., Szab\u00f3, S.: Algebra and Tiling: Homomorphisms in the Service of Geometry. The Carus Mathematical Monographs, vol.\u00a025. The Mathematical Associtaion of America (1994)","DOI":"10.5948\/UPO9781614440246"},{"key":"2_CR36","unstructured":"Haj\u00f3s, G.: Sur la factorisation des abeliens. Casopis\u00a050, 189\u2013196"},{"key":"2_CR37","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/BF01181436","volume":"46","author":"O. Perron","year":"1940","unstructured":"Perron, O.: \u00dcber l\u00fcckenlose Ausf\u00fcllung des n-dimensioanlen Raumes durch kongruente W\u00fcrfel. Math. Z.\u00a046, 161\u2013180 (1940)","journal-title":"Math. Z."},{"key":"2_CR38","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1090\/S0273-0979-1992-00318-X","volume":"27","author":"J. Lagarias","year":"1992","unstructured":"Lagarias, J., Shor, P.: Keller\u2019s Cube-Tiling Conjecture is False in High Dimensions. Bulletin AMS\u00a027, 279\u2013283 (1992)","journal-title":"Bulletin AMS"},{"key":"2_CR39","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s00454-002-2801-9","volume":"28","author":"J. Mackey","year":"2002","unstructured":"Mackey, J.: A Cube Tiling of Dimension Eight with No Facesharing. Discrete Comput. Geom.\u00a028, 275\u2013279 (2002)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"2_CR40","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF01946848","volume":"21","author":"K. Corr\u00e1di","year":"1990","unstructured":"Corr\u00e1di, K., Szab\u00f3, S.: A Combinatorial Approach for Keller\u2019s Conjecture. Periodica Math. Hung.\u00a021(2), 95\u2013100 (1990)","journal-title":"Periodica Math. Hung."},{"key":"2_CR41","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/BF01096415","volume":"3","author":"J. Hasselberg","year":"1993","unstructured":"Hasselberg, J., Pardalos, P., Vairaktarakis, G.: Test Case Generators and Computational Results for the Maximum Clique Problem. Journal of Global Optimization\u00a03, 463\u2013482 (1993)","journal-title":"Journal of Global Optimization"}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13193-6_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T22:36:21Z","timestamp":1685572581000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13193-6_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642131929","9783642131936"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13193-6_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}