{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T16:06:09Z","timestamp":1759939569125},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,1,26]],"date-time":"2007-01-26T00:00:00Z","timestamp":1169769600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2007,2,24]]},"DOI":"10.1007\/s10618-006-0053-7","type":"journal-article","created":{"date-parts":[[2007,1,25]],"date-time":"2007-01-25T20:23:49Z","timestamp":1169756629000},"page":"25-61","source":"Crossref","is-referenced-by-count":44,"title":["The complexity of non-hierarchical clustering with instance and cluster level constraints"],"prefix":"10.1007","volume":"14","author":[{"given":"Ian","family":"Davidson","sequence":"first","affiliation":[]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,1,26]]},"reference":[{"key":"53_CR1","doi-asserted-by":"crossref","unstructured":"Bansal N, Blum A, Chawla S (2002) Correlation clustering. In: Proc. 43rd annual IEEE symposium on Foundations of Computer Science (FOCS-2002), pp 238\u2013246","DOI":"10.1109\/SFCS.2002.1181947"},{"key":"53_CR2","unstructured":"Basu S, Banerjee, A, Mooney, R (2002) Semi-supervised learning by seeding. In: Proc. 19th Intl. Conf. on Machine Learning (ICML-2002). Sydney, Australia pp 19\u201326"},{"key":"53_CR3","doi-asserted-by":"crossref","unstructured":"Basu S, Bilenko M, Mooney R (2004a) A probabilistic framework for semi-supervised clustering. In: Proc. 10th ACM SIGKDD intl. conf. on knowledge discovery and data mining (KDD-2004). Seattle, WA, pp 59\u201368","DOI":"10.1145\/1014052.1014062"},{"key":"53_CR4","doi-asserted-by":"crossref","unstructured":"Basu S, Bilenko M, Mooney R (2004b) Active semi-supervision for pairwise constrained clustering. In: Proc. 4th SIAM intl. conf. on data mining (SDM-2004) pp 333\u2013344","DOI":"10.1137\/1.9781611972740.31"},{"key":"53_CR5","doi-asserted-by":"crossref","unstructured":"Bilenko M, Basu S, Mooney R (2004) Integrating constraints and metric learning in semi-supervised clustering. In: Proc. 21st international conference on on machine learning (ICML-2004), pp 11\u201318","DOI":"10.1145\/1015330.1015360"},{"key":"53_CR6","unstructured":"Bradley P, Fayyad U (1998) Refining initial points for K-Means clustering. In: Proc. 15th intl. conf. on machine learning (ICML-1998), pp 91\u201399"},{"key":"53_CR7","unstructured":"Campers G, Henkes O, Leclerq P (1987) Graph coloring heuristics: a survey, some new propositions and computational experiences on random and Leighton\u2019s graphs. In: Proc. Operational Research \u201987. Buenos Aires, pp 917\u2013932"},{"key":"53_CR8","doi-asserted-by":"crossref","unstructured":"Charikar M, Guruswami V, Wirth A (2003) Clustering with qualitative information. In: Proc. 44th Annual IEEE symposium on foundations of computer science (FOCS-2003), pp 524\u2013533","DOI":"10.1109\/SFCS.2003.1238225"},{"key":"53_CR9","doi-asserted-by":"crossref","unstructured":"Cooper GF (1990) The computational complexity of probabilistic inference using bayesian belief networks. In: Artif Intell 42(2\u20133):393\u2013405","DOI":"10.1016\/0004-3702(90)90060-D"},{"key":"53_CR10","volume-title":"Introduction to algorithms","author":"T Cormen","year":"2001","unstructured":"Cormen T, Leiserson C, Rivest R, Stein C (2001) Introduction to algorithms 2nd edn. MIT Press and McGraw-Hill, Cambridge, MA","edition":"2"},{"key":"53_CR11","doi-asserted-by":"crossref","unstructured":"Davidson I, Ravi SS (2005a) Clustering with constraints feasibility issues and the k-Means algorithm. In: Proc. 2005 SIAM International Conference on Data Mining (SDM\u201905). Newport Beach, CA, pp 138\u2013149","DOI":"10.1137\/1.9781611972757.13"},{"key":"53_CR12","doi-asserted-by":"crossref","unstructured":"Davidson I, Ravi SS (2005b) Hierarchical clustering with constraints: theory and practice. In: Proc. 9th European principles and practice of KDD (PKDD\u201905). Porto, Portugal pp 59\u201370","DOI":"10.1007\/11564126_11"},{"key":"53_CR13","doi-asserted-by":"crossref","unstructured":"Dyer M, Frieze A (1986) Planar 3DM is NP-Complete. J Algorithms :174\u2013184","DOI":"10.1016\/0196-6774(86)90002-7"},{"key":"53_CR14","unstructured":"Ester M, Kriegel H, Sander J, Xu X (1996) A density-based algorithm for discovering clusters in large spatial databases with noise. In: Proc. 2nd intl. conf. on knowledge discovery and data mining (KDD-96). Portland, OR, pp 226\u2013231"},{"key":"53_CR15","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1006\/jcss.1998.1587","volume":"57","author":"U Feige","year":"1998","unstructured":"Feige U, Kilian J (1998) Zero knowledge and the chromatic number. J Comput Syst Sci 57:187\u2013199","journal-title":"J Comput Syst Sci"},{"key":"53_CR16","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DJ (1979) Computers and intractability: a guide to the theory of NP-completeness. W H Freeman and Co., San Francisco, CA"},{"issue":"2\u20133","key":"53_CR17","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T Gonzalez","year":"1985","unstructured":"Gonzalez T (1985) Clustering to minimize the maximum intercluster distance. Theor Comput Sci 38(2\u20133):293\u2013306","journal-title":"Theor Comput Sci"},{"key":"53_CR18","first-page":"191","volume":"79","author":"P Hansen","year":"1997","unstructured":"Hansen P, Jaumard B (1997) Cluster analysis and mathematical programming. Math Program 79:191\u2013215","journal-title":"Math Program"},{"key":"53_CR19","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF02239976","volume":"39","author":"A Hertz","year":"1987","unstructured":"Hertz A, de Werra D (1987) Using Tabu search techniques for graph coloring. Computing 39:345\u2013351","journal-title":"Computing"},{"key":"53_CR20","unstructured":"Klein D, Kamvar S, Manning C (2002) From instance-level constraints to space-level constraints: making the most of prior knowledge in data clustering. In: Proc. 19th intl. conf. on machine learning (ICML 2002). Sydney, Australia, July pp 307\u2013314"},{"key":"53_CR21","doi-asserted-by":"crossref","unstructured":"Pelleg D, Moore A (1999) Accelerating exact k-means algorithms with geometric reasoning. In: Proc. ACM SIGKDD Intl. conf. on knowledge discovery and data mining. San Diego, CA pp 277\u2013281","DOI":"10.1145\/312129.312248"},{"issue":"9","key":"53_CR22","first-page":"1230","volume":"36","author":"R Tamassia","year":"1989","unstructured":"Tamassia R, Tollis I (1989) Planar grid embedding in linear time. In: IEEE Trans Circuits Syst CAS-36(9):1230\u20131234","journal-title":"In: IEEE Trans Circuits Syst CAS-"},{"key":"53_CR23","unstructured":"Wagstaff K, Cardie C (2000) Clustering with instance-level constraints. In: Proc. 17th intl. conf. on machine learning (ICML 2000). Stanford, CA, pp 1103\u20131110"},{"key":"53_CR24","unstructured":"Wagstaff K, Cardie C, Rogers S, Schroedl S (2001) Constrained K-means clustering with background knowledge. In: Proc. 18th intl. conf. on machine learning (ICML 2001). Williamstown, MA, pp 577\u2013584"},{"key":"53_CR25","unstructured":"Wagstaff K (2002) Intelligent clustering with instance-level constraints. Ph.D Thesis, Department of Computer Science, Cornell University, Ithaca, NY, Chapter 3, pp 50\u201351"},{"key":"53_CR26","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2001","unstructured":"West DB (2001) Introduction to Graph Theory 2nd edn. Prentice Hall, Inc., Englewood Cliffs, NJ","edition":"2"},{"issue":"3","key":"53_CR27","first-page":"263","volume":"2","author":"J Wijsen","year":"1998","unstructured":"Wijsen J, Meersman R (1998) On the complexity of mining quantitative association rules. In: J Data Mining Knowl Discovery 2(3):263\u2013281","journal-title":"In: J Data Mining Knowl Discovery"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-006-0053-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10618-006-0053-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-006-0053-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T19:29:39Z","timestamp":1559244579000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10618-006-0053-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1,26]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,2,24]]}},"alternative-id":["53"],"URL":"https:\/\/doi.org\/10.1007\/s10618-006-0053-7","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1,26]]}}}