{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T12:08:11Z","timestamp":1765368491598},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540311980"},{"type":"electronic","value":"9783540322177"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11611257_51","type":"book-chapter","created":{"date-parts":[[2006,1,5]],"date-time":"2006-01-05T16:37:18Z","timestamp":1136479038000},"page":"530-537","source":"Crossref","is-referenced-by-count":33,"title":["On the NP-Completeness of Some Graph Cluster Measures"],"prefix":"10.1007","author":[{"given":"Ji\u0159\u00ed","family":"\u0160\u00edma","sequence":"first","affiliation":[]},{"given":"Satu Elisa","family":"Schaeffer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-2","key":"51_CR1","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-Completeness Results for Cubic Graphs. Theoretical Computer Science\u00a0237(1-2), 123\u2013134 (2000)","journal-title":"Theoretical Computer Science"},{"key":"51_CR2","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1145\/1007352.1007355","volume-title":"Proceedings of the STOC 2004 Thirty-Sixth Annual ACM Symposium on Theory of Computing","author":"S. Arora","year":"2004","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander Flows, Geometric Embeddings and Graph Partitioning. In: Proceedings of the STOC 2004 Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 222\u2013231. ACM Press, New York (2004)"},{"issue":"1-3","key":"51_CR3","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N. Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation Clustering. Machine Learning\u00a056(1-3), 89\u2013113 (2004)","journal-title":"Machine Learning"},{"key":"51_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/978-3-540-39658-1_52","volume-title":"Algorithms - ESA 2003","author":"U. Brandes","year":"2003","unstructured":"Brandes, U., Gaertler, M., Wagner, D.: Experiments on Graph Clustering Algorithms. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 568\u2013579. Springer, Heidelberg (2003)"},{"issue":"1-6","key":"51_CR5","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/S1389-1286(00)00083-9","volume":"33","author":"A. Broder","year":"2000","unstructured":"Broder, A., Kumar, S.R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.: Graph Structure in the Web. Computer Networks\u00a033(1-6), 309\u2013320 (2000)","journal-title":"Computer Networks"},{"issue":"2","key":"51_CR6","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF02579448","volume":"7","author":"T.N. Bui","year":"1987","unstructured":"Bui, T.N., Chaudhuri, S., Leighton, F.T., Sipser, M.: Graph Bisection Algorithms with Good Average Case Behavior. Combinatorica\u00a07(2), 171\u2013191 (1987)","journal-title":"Combinatorica"},{"key":"51_CR7","unstructured":"Carrasco, J.J., Fain, D.C., Lang, K.J., Zhukov, L.: Clustering of Bipartite Advertiser-Keyword Graph. In: The ICDM 2003 Third IEEE International Conference on Data Mining, Workshop on Clustering Large Data Sets, Melbourne, Florida (2003)"},{"key":"51_CR8","doi-asserted-by":"crossref","unstructured":"Cheng, D., Kannan, R., Vempala, S., Wang, G.: A Divide-and-Merge Methodology for Clustering. In: Proceedings of the PODS 2005 Twenty-Fourth ACM Symposium on Principles of Database Systems, Baltimore (June 2005)","DOI":"10.1145\/1065167.1065192"},{"key":"51_CR9","unstructured":"Flake, G.W., Tsioutsiouliklis, K., Tarjan, R.E.: Graph Clustering Techniques Based on Minimum-Cut Trees. Technical report 2002-06, NEC, Princeton, NJ (2002)"},{"key":"51_CR10","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.\u00a0H.\u00a0Freeman & Co., San Francisco (1979)"},{"key":"51_CR11","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1145\/781027.781046","volume-title":"Proceedings of the SIGMETRICS 2003 ACM International Conference on Measurement and Modeling of Computer Systems","author":"C. Gkantsidis","year":"2003","unstructured":"Gkantsidis, C., Mihail, M., Saberi, A.: Conductance and Congestion in Power Law Graphs. In: Proceedings of the SIGMETRICS 2003 ACM International Conference on Measurement and Modeling of Computer Systems, pp. 148\u2013159. ACM Press, New York (2003)"},{"key":"51_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-44849-7_25","volume-title":"Algorithms and Complexity","author":"K. Holzapfel","year":"2003","unstructured":"Holzapfel, K., Kosub, S., Maa\u00df, M.G., T\u00e4ubig, H.: The Complexity of Detecting Fixed-Density Clusters. In: Petreschi, R., Persiano, G., Silvestri, R. (eds.) CIAC 2003. LNCS, vol.\u00a02653, pp. 201\u2013212. Springer, Heidelberg (2003)"},{"issue":"3","key":"51_CR13","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1145\/331499.331504","volume":"31","author":"A.K. Jain","year":"1999","unstructured":"Jain, A.K., Murty, M.N., Flynn, P.J.: Data Clustering: A Review. ACM Computing Surveys\u00a031(3), 264\u2013323 (1999)","journal-title":"ACM Computing Surveys"},{"key":"51_CR14","unstructured":"Kaibel, V.: On the Expansion of Graphs of 0\/1-Polytopes. Technical report arXiv:math.CO\/0112146 (2001)"},{"key":"51_CR15","first-page":"367","volume-title":"Proceedings of the FOCS 2000 Forty-First Annual Symposium on the Foundation of Computer Science","author":"R. Kannan","year":"2000","unstructured":"Kannan, R., Vempala, S., Vetta, A.: On Clusterings: Good, Bad and Spectral. In: Proceedings of the FOCS 2000 Forty-First Annual Symposium on the Foundation of Computer Science, pp. 367\u2013377. IEEE Computer Society Press, New York (2000)"},{"key":"51_CR16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"issue":"6","key":"51_CR17","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"T. Leighton","year":"1999","unstructured":"Leighton, T., Rao, S.: Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms. Journal of the ACM\u00a046(6), 787\u2013832 (1999)","journal-title":"Journal of the ACM"},{"key":"51_CR18","first-page":"353","volume":"2","author":"L. Lov\u00e1sz","year":"1996","unstructured":"Lov\u00e1sz, L.: Random Walks on Graphs: A Survey. Bolyai Society Mathematical Studies, 2, Combinatorics, Paul Erd\u00f6s is Eighty, Budapest: Bolyai Mathematical Society\u00a02, 353\u2013397 (1996)","journal-title":"Bolyai Society Mathematical Studies, 2, Combinatorics, Paul Erd\u00f6s is Eighty, Budapest: Bolyai Mathematical Society"},{"key":"51_CR19","unstructured":"Mihail, M., Gkantsidis, C., Saberi, A., Zegura, E.: On the Semantics of Internet Topologies. Technical Report GIT-CC-02-07, College of Computing, Georgia Institute of Technology, Atlanta, GA (2002)"},{"key":"51_CR20","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/11430919_42","volume-title":"Advances in Knowledge Discovery and Data Mining","author":"S.E. Schaeffer","year":"2005","unstructured":"Schaeffer, S.E.: Stochastic Local Clustering for Massive Graphs. In: Ho, T.-B., Cheung, D., Liu, H. (eds.) PAKDD 2005. LNCS (LNAI), vol.\u00a03518, pp. 354\u2013360. Springer, Heidelberg (2005)"},{"key":"51_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/3-540-36379-3_33","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"R. Shamir","year":"2002","unstructured":"Shamir, R., Sharan, R., Tsur, D.: Cluster Graph Modification Problems. In: Ku\u010dera, L. (ed.) WG 2002. LNCS, vol.\u00a02573, pp. 379\u2013390. Springer, Heidelberg (2002)"},{"issue":"8","key":"51_CR22","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J. Shi","year":"2000","unstructured":"Shi, J., Malik, J.: Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a022(8), 888\u2013905 (2000)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"51_CR23","unstructured":"Virtanen, S.E.: Properties of Nonuniform Random Graph Models. Technical Report HUT-TCS-A77, Laboratory for Theoretical Computer Science, Helsinki University of Technology, Espoo, Finland (2003)"},{"key":"51_CR24","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1145\/800133.804355","volume-title":"Proceedings of the STOC 1978 Tenth Annual ACM Symposium on Theory of Computing","author":"M. Yannakakis","year":"1978","unstructured":"Yannakakis, M.: Node- and Edge-Deletion NP-Complete Problems. In: Proceedings of the STOC 1978 Tenth Annual ACM Symposium on Theory of Computing, pp. 253\u2013264. ACM Press, New York (1978)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2006: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11611257_51.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:09:42Z","timestamp":1619507382000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11611257_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540311980","9783540322177"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11611257_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}