{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T04:29:38Z","timestamp":1768105778662,"version":"3.49.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,3,14]],"date-time":"2013-03-14T00:00:00Z","timestamp":1363219200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2013,9]]},"DOI":"10.1007\/s10589-013-9548-5","type":"journal-article","created":{"date-parts":[[2013,3,13]],"date-time":"2013-03-13T19:16:39Z","timestamp":1363202199000},"page":"113-130","source":"Crossref","is-referenced-by-count":41,"title":["Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations"],"prefix":"10.1007","volume":"56","author":[{"given":"Svyatoslav","family":"Trukhanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chitra","family":"Balasubramaniam","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Balabhaskar","family":"Balasundaram","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergiy","family":"Butenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,3,14]]},"reference":[{"key":"9548_CR1","series-title":"DIMACS Series on Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1090\/dimacs\/050\/06","volume-title":"External Memory Algorithms and Visualization","author":"J. Abello","year":"1999","unstructured":"Abello, J., Pardalos, P.M., Resende, M.G.C.: On maximum clique problems in very large graphs. In: Abello, J., Vitter, J. (eds.) External Memory Algorithms and Visualization. DIMACS Series on Discrete Mathematics and Theoretical Computer Science, vol. 50, pp. 119\u2013130. American Mathematical Society, Providence (1999)"},{"key":"9548_CR2","unstructured":"Applegate, D., Johnson, D.S.: dfmax.c [c program, second dimacs implementation challenge]. http:\/\/dimacs.rutgers.edu\/pub\/challenge\/graph\/solvers\/"},{"issue":"4","key":"9548_CR3","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1007\/BF02257777","volume":"46","author":"L. Babel","year":"1991","unstructured":"Babel, L.: Finding maximum cliques in arbitrary and in special graphs. Computing 46(4), 321\u2013341 (1991)","journal-title":"Computing"},{"issue":"1","key":"9548_CR4","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1038\/nbt924","volume":"22","author":"J.S. Bader","year":"2004","unstructured":"Bader, J.S., Chaudhuri, A., Rothberg, J.M., Chant, J.: Gaining confidence in high-throughput protein interaction networks. Nat. Biotechnol. 22(1), 78\u201385 (2004)","journal-title":"Nat. Biotechnol."},{"key":"9548_CR5","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/BF01955041","volume":"15","author":"E. Balas","year":"1996","unstructured":"Balas, E., Xue, J.: Weighted and unweighted maximum clique algorithms with upper bounds from fractional coloring. Algorithmica 15, 397\u2013412 (1996)","journal-title":"Algorithmica"},{"key":"9548_CR6","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1137\/0215075","volume":"15","author":"E. Balas","year":"1986","unstructured":"Balas, E., Yu, C.: Finding a maximum clique in an arbitrary graph. SIAM J. Comput. 15, 1054\u20131068 (1986)","journal-title":"SIAM J. Comput."},{"key":"9548_CR7","unstructured":"Balasundaram, B.: Graph theoretic generalizations of clique: optimization and extensions. PhD thesis, Texas A&M University, College Station, Texas, USA (2007)"},{"issue":"1","key":"9548_CR8","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1287\/opre.1100.0851","volume":"59","author":"B. Balasundaram","year":"2011","unstructured":"Balasundaram, B., Butenko, S., Hicks, I.V.: Clique relaxations in social network analysis: the maximum k-plex problem. Oper. Res. 59(1), 133\u2013142 (2011)","journal-title":"Oper. Res."},{"issue":"1","key":"9548_CR9","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/s10878-005-1857-x","volume":"10","author":"B. Balasundaram","year":"2005","unstructured":"Balasundaram, B., Butenko, S., Trukhanov, S.: Novel approaches for analyzing biological networks. J. Comb. Optim. 10(1), 23\u201339 (2005)","journal-title":"J. Comb. Optim."},{"key":"9548_CR10","volume-title":"Handbook of Combinatorial Optimization","author":"B. Balasundaram","year":"2013","unstructured":"Balasundaram, B., Mahdavi Pajouh, F.: Graph theoretic clique relaxations and applications. In: Pardalos, P.M., Du, D.-Z., Graham, R. (eds.) Handbook of Combinatorial Optimization, 2nd edn. Springer, Berlin (2013). doi: 10.1007\/978-1-4419-7997-1_9","edition":"2"},{"key":"9548_CR11","doi-asserted-by":"crossref","first-page":"3171","DOI":"10.1016\/j.cor.2005.01.027","volume":"33","author":"V. Boginski","year":"2006","unstructured":"Boginski, V., Butenko, S., Pardalos, P.: Mining market data: a network approach. Comput. Oper. Res. 33, 3171\u20133184 (2006)","journal-title":"Comput. Oper. Res."},{"key":"9548_CR12","volume-title":"Innovation in Financial and Economic Networks","author":"V. Boginski","year":"2003","unstructured":"Boginski, V., Butenko, S., Pardalos, P.M.: On structural properties of the market graph. In: Nagurney, A. (ed.) Innovation in Financial and Economic Networks. Edward Elgar, London (2003)"},{"key":"9548_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4757-3023-4_1","volume-title":"Handbook of Combinatorial Optimization","author":"I.M. Bomze","year":"1999","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, pp. 1\u201374. Kluwer Academic, Dordrecht (1999)"},{"key":"9548_CR14","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C. Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques on an undirected graph. Commun. ACM 16, 575\u2013577 (1973)","journal-title":"Commun. ACM"},{"key":"9548_CR15","doi-asserted-by":"crossref","first-page":"1334","DOI":"10.1109\/18.59932","volume":"36","author":"A. Brouwer","year":"1990","unstructured":"Brouwer, A., Shearer, J., Sloane, N., Smith, W.: A new table of constant weight codes. IEEE Trans. Inf. Theory 36, 1334\u20131380 (1990)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9548_CR16","doi-asserted-by":"crossref","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. Eur. J. Oper. Res. 173, 1\u201317 (2006)","journal-title":"Eur. J. Oper. Res."},{"key":"9548_CR17","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","volume":"9","author":"R. Carraghan","year":"1990","unstructured":"Carraghan, R., Pardalos, P.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9, 375\u2013382 (1990)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"9548_CR18","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1002\/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T","volume":"24","author":"L. Cowen","year":"1997","unstructured":"Cowen, L., Goddard, W., Jesurum, C.E.: Defective coloring revisited. J. Graph Theory 24(3), 205\u2013219 (1997)","journal-title":"J. Graph Theory"},{"key":"9548_CR19","unstructured":"Dimacs. Cliques, Coloring, and Satisfiability: Second Dimacs Implementation Challenge (1995). Online: http:\/\/dimacs.rutgers.edu\/Challenges\/ . Accessed March 2007"},{"key":"9548_CR20","unstructured":"Dimacs. Graph partitioning and graph clustering: tenth Dimacs implementation challenge (2011). Online: http:\/\/www.cc.gatech.edu\/dimacs10\/index.shtml . Accessed July 2012"},{"key":"9548_CR21","series-title":"Annals of Discrete Mathematics","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/S0167-5060(08)70374-1","volume-title":"Quo Vadis, Graph Theory?","author":"M. Frik","year":"1993","unstructured":"Frik, M.: A survey of (m,k)-colorings. In: Gimbel, J., Kennedy, J.W., Quintas, L.V. (eds.) Quo Vadis, Graph Theory? Annals of Discrete Mathematics, vol. 55, pp. 45\u201358. Elsevier, New York (1993)"},{"key":"9548_CR22","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. W.H. Freeman, New York (1979)"},{"issue":"4","key":"9548_CR23","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01096415","volume":"3","author":"J. Hasselberg","year":"1993","unstructured":"Hasselberg, J., Pardalos, P.M., Vairaktarakis, G.: Test case generators and computational results for the maximum clique problem. J. Glob. Optim. 3(4), 463\u2013482 (1993)","journal-title":"J. Glob. Optim."},{"key":"9548_CR24","doi-asserted-by":"crossref","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\u2212\u03b5 . Acta Math. 182, 105\u2013142 (1999)","journal-title":"Acta Math."},{"key":"9548_CR25","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume-title":"Cliques, Coloring, and Satisfiablility: Second Dimacs Implementation Challenge","year":"1996","unstructured":"Johnson, D.S., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiablility: Second Dimacs Implementation Challenge. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26. American Mathematical Society, Providence (1996)"},{"key":"9548_CR26","first-page":"1","volume-title":"Proceedings of the USENIX Symposium on Location Independent and Mobile Computing","author":"P. Krishna","year":"1995","unstructured":"Krishna, P., Chatterjee, M., Vaidya, N.H., Pradhan, D.K.: A cluster-based approach for routing in ad-hoc networks. In: Proceedings of the USENIX Symposium on Location Independent and Mobile Computing, pp. 1\u20138 (1995)"},{"key":"9548_CR27","unstructured":"Leskovec, J.: Stanford network analysis project (2012). http:\/\/snap.stanford.edu\/data\/"},{"issue":"2","key":"9548_CR28","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"J.M. Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J.\u00a0Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9548_CR29","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/3-540-56939-1_60","volume-title":"Proceedings of the 20th International Colloquium on Automata, Languages and Programming, ICALP \u201993","author":"C. Lund","year":"1993","unstructured":"Lund, C., Yannakakis, M.: The approximation of maximum subgraph problems. In: Proceedings of the 20th International Colloquium on Automata, Languages and Programming, ICALP \u201993, pp. 40\u201351. Springer, London (1993)"},{"key":"9548_CR30","unstructured":"McClosky, B.: Independence systems and stable set relaxations. PhD thesis, Rice University (2008)"},{"issue":"3","key":"9548_CR31","doi-asserted-by":"crossref","first-page":"1135","DOI":"10.1137\/070687414","volume":"23","author":"B. McClosky","year":"2009","unstructured":"McClosky, B., Hicks, I.V.: The co-2-plex polytope and integral systems. SIAM J. Discrete Math. 23(3), 1135\u20131148 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"9548_CR32","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/s10878-010-9338-2","volume":"23","author":"B. McClosky","year":"2012","unstructured":"McClosky, B., Hicks, I.V.: Combinatorial algorithms for the maximum k-plex problem. J. Comb. Optim. 23, 29\u201349 (2012)","journal-title":"J. Comb. Optim."},{"key":"9548_CR33","doi-asserted-by":"crossref","unstructured":"Moser, H., Niedermeier, R., Sorge, M.: Exact combinatorial algorithms and experiments for finding maximum k-plexes. J. Combin. Optim., 1\u201327 (2011). doi: 10.1007\/s10878-011-9391-5","DOI":"10.1007\/s10878-011-9391-5"},{"key":"9548_CR34","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S1571-0653(05)80045-9","volume":"3","author":"P.R.J. \u00d6sterg\u00e5rd","year":"1999","unstructured":"\u00d6sterg\u00e5rd, P.R.J.: A new algorithm for the maximum-weight clique problem. Electron. Notes Discrete Math. 3, 153\u2013156 (1999)","journal-title":"Electron. Notes Discrete Math."},{"key":"9548_CR35","doi-asserted-by":"crossref","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 Appl. Math. 120, 197\u2013207 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9548_CR36","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1007\/s11590-010-0225-7","volume":"5","author":"P.R.J. \u00d6sterg\u00e5rd","year":"2011","unstructured":"\u00d6sterg\u00e5rd, P.R.J., Vaskelainen, V.P.: Russian Doll search for the Steiner triple covering problem. Optim. Lett. 5(4), 631\u2013638 (2011)","journal-title":"Optim. Lett."},{"key":"9548_CR37","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/j.ejor.2012.10.021","volume":"226","author":"J. Pattillo","year":"2013","unstructured":"Pattillo, J., Youssef, N., Butenko, S.: On clique relaxation models in network analysis. Eur. J. Oper. Res. 226, 9\u201318 (2013)","journal-title":"Eur. J. Oper. Res."},{"key":"9548_CR38","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1109\/INFCOM.1989.101493","volume-title":"Proceedings of the Eighth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM \u201989)","author":"R. Ramaswami","year":"1989","unstructured":"Ramaswami, R., Parhi, K.K.: Distributed scheduling of broadcasts in a radio network. In: Proceedings of the Eighth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM \u201989), vol. 2, pp. 497\u2013504 (1989)"},{"key":"9548_CR39","volume-title":"Social Network Analysis: A Handbook","author":"J. Scott","year":"2000","unstructured":"Scott, J.: Social Network Analysis: A Handbook, 2nd edn. Sage Publications, London (2000)","edition":"2"},{"key":"9548_CR40","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1080\/0022250X.1978.9989883","volume":"6","author":"S.B. Seidman","year":"1978","unstructured":"Seidman, S.B., Foster, B.L.: A graph theoretic generalization of the clique concept. J. Math. Sociol. 6, 139\u2013154 (1978)","journal-title":"J. Math. Sociol."},{"issue":"4","key":"9548_CR41","doi-asserted-by":"crossref","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. Comput. 10(4), 438\u2013447 (1998)","journal-title":"INFORMS J. Comput."},{"key":"9548_CR42","first-page":"11","volume":"18","author":"N.J.A. Sloane","year":"1989","unstructured":"Sloane, N.J.A.: Unsolved problems in graph theory arising from the study of codes. Graph Theory Notes N. Y. 18, 11\u201320 (1989)","journal-title":"Graph Theory Notes N. Y."},{"key":"9548_CR43","unstructured":"Sloane, N.J.A.: Challenge problems: Independent sets in graphs (2000). Online: http:\/\/www.research.att.com\/~njas\/doc\/graphs.html . Accessed July 2003"},{"key":"9548_CR44","series-title":"Ohio State University Mathematical Research Institute Publications","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1515\/9783110198119.273","volume-title":"Codes and Designs","author":"N.J.A. Sloane","year":"2002","unstructured":"Sloane, N.J.A.: On single-deletion-correcting codes. In: Arasu, K.T., Seress, A. (eds.) Codes and Designs. Ohio State University Mathematical Research Institute Publications, vol. 10, pp. 273\u2013291. Walter de Gruyter, Berlin (2002)"},{"issue":"1","key":"9548_CR45","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/s10898-006-9039-7","volume":"37","author":"E. Tomita","year":"2007","unstructured":"Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Glob. Optim. 37(1), 95\u2013111 (2007)","journal-title":"J. Glob. Optim."},{"key":"9548_CR46","unstructured":"Vaskelainen, V.: Russian Doll Search algorithms for discrete optimization problems. PhD thesis, Helsinki University of Technology (2010)"},{"key":"9548_CR47","first-page":"181","volume-title":"Proceedings of the National Conference on Artificial Intelligence","author":"G. Verfaillie","year":"1996","unstructured":"Verfaillie, G., Lemaitre, M., Schiex, T.: Russian Doll Search for solving constraint optimization problems. In: Proceedings of the National Conference on Artificial Intelligence, pp. 181\u2013187. Citeseer, Princeton (1996)"},{"key":"9548_CR48","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511815478","volume-title":"Social Network Analysis","author":"S. Wasserman","year":"1994","unstructured":"Wasserman, S., Faust, K.: Social Network Analysis. Cambridge University Press, New York (1994)"},{"issue":"5","key":"9548_CR49","doi-asserted-by":"crossref","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. Oper. Res. Lett. 21(5), 211\u2013217 (1997)","journal-title":"Oper. Res. Lett."},{"key":"9548_CR50","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/800133.804355","volume-title":"STOC \u201978: Proceedings of the 10th Annual ACM Symposium on Theory of Computing","author":"M. Yannakakis","year":"1978","unstructured":"Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: STOC \u201978: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 253\u2013264. ACM Press, New York (1978)"},{"issue":"4","key":"9548_CR51","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1145\/322154.322157","volume":"26","author":"M. Yannakakis","year":"1979","unstructured":"Yannakakis, M.: The effect of a connectivity requirement on the complexity of maximum subgraph problems. J. ACM 26(4), 618\u2013630 (1979)","journal-title":"J. ACM"},{"issue":"7","key":"9548_CR52","doi-asserted-by":"crossref","first-page":"823","DOI":"10.1093\/bioinformatics\/btl014","volume":"22","author":"H. Yu","year":"2006","unstructured":"Yu, H., Paccanaro, A., Trifonov, V., Gerstein, M.: Predicting interactions in protein networks by completing defective cliques. Bioinformatics 22(7), 823\u2013829 (2006)","journal-title":"Bioinformatics"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-013-9548-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-013-9548-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-013-9548-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T08:16:54Z","timestamp":1688113014000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-013-9548-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,14]]},"references-count":52,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["9548"],"URL":"https:\/\/doi.org\/10.1007\/s10589-013-9548-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,14]]}}}