{"entities":{"Q1102746":{"pageid":1113498,"ns":120,"title":"Item:Q1102746","lastrevid":49167379,"modified":"2026-01-06T17:01:24Z","type":"item","id":"Q1102746","labels":{"en":{"language":"en","value":"NP-hard problems in hierarchical-tree clustering"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4050985"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$0BFA6B59-F4F5-45A9-9B08-8F27342C0978","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b6612582274643bf772595865f245c5bf21dc43b","datavalue":{"value":{"text":"NP-hard problems in hierarchical-tree clustering","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1102746$C72E2BFE-1967-401E-872F-BC0F08182B65","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dff5150849b60b7f021dde9491ae3c648dafe012","datavalue":{"value":"0644.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102746$4C42BF12-8BB8-41D3-9232-8D30E7C66E96","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"53c8c40decae43de057fffb52df82b6f6fc2262b","datavalue":{"value":"10.1007/BF00289116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102746$CD4E4093-A698-444E-9EF8-181B2B07E6F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f599934ad10d19e2cb67f86f48d0ea65a928295","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$1ED2EF25-2057-4F12-A205-BDD5C5FC4DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e8a024c58c52edbf6f78834de8cd7b07e4afcf76","datavalue":{"value":{"entity-type":"item","numeric-id":1102745,"id":"Q1102745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$548E3F41-4A97-45E1-9F85-1D5AEB68060F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$DEBF0ECB-714E-4A8E-B35D-001CAF4D0972","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1102746$BB40FEA3-B2D0-465D-9776-669309D92C88","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"230452a8710e52779af8972406e1b4ca914b2e63","datavalue":{"value":"Given an n-element set \\(X=\\{x_ 1,...,x_ n\\}\\) and a symmetric matrix \\(D=(d_{i,j})\\) whose elements are 0 on the diagonal and positive real numbers elsewhere, a hierarchical tree T over X is defined as a sequence of pairs \\((P_ i, l_ i)\\) \\((i=1,...,q)\\) where the \\(P_ i\\) are partitions of X such that \\(P_ 1=\\{\\{x_ 1\\}\\), \\(\\{x_ 2\\},...,\\{x_ n\\}\\}\\), \\(P_ q=\\{X\\}\\) and \\(P_ i\\) is a proper refinement of \\(P_{i+1}\\) (1\\(\\leq i\\leq q-1)\\), and the \\(l_ i\\) are integers with \\(0=l_ 1<l_ 2<...<l_ q\\). The integer q is called the height of T and \\(l_ k\\) the level of \\(P_ k\\) in T. If \\(d_{i,j}\\) is a measure of ``dissimilarity'' among elements \\(x_ i\\) and \\(x_ j\\), the hierarchical clustering problem (HIC) is intuitively the problem of finding a hierarchical tree \\(T^*\\) over X which is ``optimal'' in the sense that it minimizes the difference among the dissimilarity of two elements and the level in the tree where they appear for the first time in the same class in the partition.    More formally, the tree \\(T^*\\) should minimize the value of an objective function F, defined from the set of hierarchical trees on X to the set of nonnegative reals, as follows:  \\[  F(T)=\\sum_{1\\leq i<j\\leq n}| d_{i,j}-u_ T(x_ i,x_ j)| \\]  where \\(u_ T\\) is the function:  \\[  u_ T(x_ i,x_ j)=Min\\{l_ k | \\quad \\exists M\\in P_ k\\quad such\\quad that\\quad \\{x_ i,x_ j\\}\\subseteq M\\}\\quad.  \\]  A variant of the problem, called \\(HIC_ q\\), consists in finding the optimal tree of a fixed height q (2\\(\\leq q\\leq n).\\)    In the paper it is shown that problems HIC and \\(HIC_ q\\), for \\(q\\geq 3\\), are NP-hard.    The proof is based on a chain of polynomial reductions. First, it is shown that \\(HIC_ q\\propto HIC_{q+1}\\), where \\(\\propto\\) denotes the polynomial reducibility relation. Then, the binary restrictions \\({}^ bHIC\\) and \\({}^ bHIC_ q\\) of the above problems, i.e. the restrictions to dissimilarity matrices in which each off-diagonal element equals either 1 or 2, are considered, and it is proved that \\({}^ bHIC_ 3\\propto^ bHIC\\). At this point, the NP-hardness of \\({}^ bHIC_ 3\\) is proved by reduction from the NP-complete problem EC3 (exact cover by ordered 3-tuples): \\(EC3\\propto^ bHIC_ 3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102746$CF2050A8-9DD0-474F-B135-8519B3DC35ED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102746$8A14D8B5-57D6-4C00-B195-16A43D283A6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102746$57F36910-D79F-44E7-B2D1-7AA01432A087","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"843de71235f44a800ae389e1734df6bb7650efec","datavalue":{"value":"65K10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102746$E199F902-CB2F-4FB4-A6AA-A9A873F85C81","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f966992039903a6318c536035c27c68028717b53","datavalue":{"value":"4050985","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102746$2F116745-CFCF-4169-8DCF-4A6BFF4B06C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e64d3057bacf1d360d2716fa3007c734d08c602c","datavalue":{"value":"cluster analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102746$1516DD99-5231-4F00-AD7D-80B38E00F6FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a59b1493a3dfce77efe9c02f17396ec193aeaaf0","datavalue":{"value":"optimization problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102746$B755E927-EC7C-48D8-9A8F-954E5BE3C827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90564594f123f0e66a700965354ed64d824a5ed0","datavalue":{"value":"hierarchical-tree clustering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102746$5DB856A7-1A1F-466D-8D14-35DB1C6CC798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102746$4D4DA3C0-26B7-473C-A583-F9CCEE81A403","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$D918B85D-EBB7-40B4-88ED-0010C4ED888B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d7857aa75f43cb523906c8d1acdc973ae33ed49","datavalue":{"value":{"entity-type":"item","numeric-id":4054519,"id":"Q4054519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$0732FB6F-0CD8-4010-A3F2-B8323E0400F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$CD3B9D0C-F01D-448B-B97F-744E8FBA2B27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7033dd94767bf10e2700f8a7bd5817e2ced0a30","datavalue":{"value":{"entity-type":"item","numeric-id":4148820,"id":"Q4148820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$8C04FD67-3716-45D6-9382-82CB9D9BE291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb22ae813b2fa2dfe63254eb24d25bb03a9f46b8","datavalue":{"value":{"entity-type":"item","numeric-id":3670385,"id":"Q3670385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$8172F73B-8383-44D9-BAB8-AFBF8CD50624","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcf6016aa6a6bb4076c71393c202be8c4bc90220","datavalue":{"value":{"entity-type":"item","numeric-id":4085109,"id":"Q4085109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$F1F8211D-F4AA-40C3-B9CC-92B62EE25A18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b23be84fe3a80caf9de45c5ba219262074b0f02a","datavalue":{"value":{"entity-type":"item","numeric-id":2012662,"id":"Q2012662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$35BD9038-39F2-4465-ADEE-244E5F45E87E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1ee171961e6c8a78cc8dd53028ae065c15cd9e4","datavalue":{"value":{"entity-type":"item","numeric-id":3698098,"id":"Q3698098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$55FCDAD9-35CB-4DE1-AABF-59A69517F8D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac0ec4868dba1b37d1adb8bb9f6a23d6c0a862f5","datavalue":{"value":{"entity-type":"item","numeric-id":3880849,"id":"Q3880849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$D0980F73-5805-400A-BF23-BBC55C7E5955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f9d6f13bf2ecd99de6a96a3d332ae34b3532cee","datavalue":{"value":{"entity-type":"item","numeric-id":3875132,"id":"Q3875132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$1D433D91-0CD4-43B6-8EBC-C9594AF4D413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5461b2cdafe91b12a53e2a4c71fe615efb2aa2fd","datavalue":{"value":{"entity-type":"item","numeric-id":5337832,"id":"Q5337832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102746$E43CAECA-535B-4A42-BFBD-76792C53F524","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7d063d8dccdb1c2aec2671c1f39e2474c9fcdc9d","datavalue":{"value":"https://doi.org/10.1007/bf00289116","type":"string"},"datatype":"url"},"type":"statement","id":"Q1102746$0D132FBB-6CF8-4E8D-A4F0-4E53D389AC06","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"43169dc4c4820d69ac3a810d4197104ed6da8446","datavalue":{"value":"W2055764977","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102746$F97730CB-76C7-4F35-B137-F83EE2197FAF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ae54c62d534169be4bb547502e3ffdc0efdba95","datavalue":{"value":{"entity-type":"item","numeric-id":3698098,"id":"Q3698098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c8c9838c7f1986e73cc7302d9810fb2fd7d0555","datavalue":{"value":{"amount":"+0.9135214686393738","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102746$8A19F6FD-1523-4AA6-8F1B-8EC976AD74DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5eeb1374bdb3b826e95e59ecafc1f5a5a25899b","datavalue":{"value":{"entity-type":"item","numeric-id":1566100,"id":"Q1566100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47b536d529625984f515eff5b48dd93c390574cc","datavalue":{"value":{"amount":"+0.8244428634643555","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102746$68E6ABAD-F880-4A14-8D44-A00E4A440605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3afbce2c16fd909c61350e4d242948284963978","datavalue":{"value":{"entity-type":"item","numeric-id":3703127,"id":"Q3703127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63767323e8a1c2d01a766f74347de728f1a80fa5","datavalue":{"value":{"amount":"+0.8208013772964478","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102746$EC25F100-88AE-4487-B080-88939097868D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0384767f4e0cde3fe54d20cdf55ed118674dc73f","datavalue":{"value":{"entity-type":"item","numeric-id":1028427,"id":"Q1028427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7a191269ed7c07aa18c08a77a2774dd087914c9","datavalue":{"value":{"amount":"+0.8096385598182678","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102746$D3CFD746-E561-47DC-A9CC-B09548961FFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf0684287e85d89491cebc12cbabe4f5ba97963e","datavalue":{"value":{"entity-type":"item","numeric-id":1392041,"id":"Q1392041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b5b95f8d3b652e6e4dd4de378f4af471f87325c","datavalue":{"value":{"amount":"+0.80775386095047","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1102746$839394F2-768C-4613-B88C-F5C6CC010414","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1102746","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1102746"}}}}}