{"entities":{"Q1842652":{"pageid":1853394,"ns":120,"title":"Item:Q1842652","lastrevid":69096621,"modified":"2026-04-13T04:45:48Z","type":"item","id":"Q1842652","labels":{"en":{"language":"en","value":"Hypercube embedding of generalized bipartite metrics"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 750903"}},"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":"Q1842652$C80EEEBD-AE30-4515-A398-93BAEC10FE8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bc5c5f4ce0c03cf02a5896cbd1231fca36c37a1b","datavalue":{"value":{"text":"Hypercube embedding of generalized bipartite metrics","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1842652$2251EB1D-8ABB-4165-B7CB-491A67B205D1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5383d04221d0f6bd1c04df76ffe2caa6b1cc1942","datavalue":{"value":"0821.05017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842652$E907285B-A9CE-4F68-A9C3-32EB86684CFD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7eaa68b9964455e6b4927b720f860f307becb77b","datavalue":{"value":"10.1016/0166-218X(94)00087-T","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842652$460827FD-58E3-49F8-A5CE-2C6DFCFC324D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7df8fff1441ef18744fe1dd7a53aa93a08c6730","datavalue":{"value":{"entity-type":"item","numeric-id":344892,"id":"Q344892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$F734AAF5-41B1-4366-93A3-4C13C624081A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6f64edf73f993816256602ea6ed8ba550f1c19e7","datavalue":{"value":{"entity-type":"item","numeric-id":1031083,"id":"Q1031083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$0BF89415-1022-42A2-B9C5-C00B2DB71454","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$4BA5F333-5182-4450-991F-F5E777747B85","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8d4fc7d5b9d9d0934d8c607493710e4d4f473b95","datavalue":{"value":{"time":"+1995-10-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1842652$C6C9E8EF-8149-4E10-898C-BA36B4D7DA57","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8da92b32fbe3293b1707ef118d02f58560e71323","datavalue":{"value":"The authors consider a case of the general problem of a metric which is called \\(h\\)-embeddability. The question is ``whether for a given hypercube containing \\(n\\)-dimensional binary vectors and for a given metric \\(d(x,y)\\), there exist \\(n\\) vectors \\(v_ 1,v_ 2,\\dots, v_ n\\) for which the Hamming distance between each two vectors \\(v_ x\\), \\(v_ y\\) equals \\(d(x,y)\\)?'' The general problem is NP-complete. However, there are known numerous general instances for which \\(h\\)-embeddability of a given metric can be tested in polynomial time. The main objective of the paper consists in showing that for generalized \\(h\\)-embeddable bipartite metrics the problem can be solved in polynomial time. Also given is a polynomial time algorithm for the recognition of the \\(h\\)-embeddability of a given metric. The problem is considered in a very general way giving important and practical knowledge concerning properties of metrics defined in a hypercube.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842652$3C5CC97B-9942-410A-9E5A-2F434E9E2CF3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842652$8C17D80B-51CC-43CD-A210-E8A38E1E59DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842652$5352291F-6F5F-4CB5-BFDD-87FE13141292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842652$E008F303-B6EB-4F9B-A83A-32A921BEB498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842652$5B74D8E0-72B7-4971-B023-EE82F21FFC44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7b8a0eac350755739664ad3ee71bd5c4641e7532","datavalue":{"value":"750903","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842652$B5790503-6EDD-4B63-88F7-2E51521BF458","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a08c106d601d7d8786667854db64f3b19e5e709","datavalue":{"value":"\\(h\\)-embeddability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842652$6DBBB03E-09DF-42FC-BB22-6A8215DE92FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842652$E9742BDF-68AB-4304-8FAF-A2B14D8865D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7e507470f9b21b1d2b7c7e2c1808bd7d3af3f83","datavalue":{"value":"Hamming distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842652$A33C6474-45D5-4053-856E-B380513AAB42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842652$60FAD692-CFBA-4335-8127-59DFBDF0A9C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89a5b384fe56aed5d50e6d8580a25954d8d28a2b","datavalue":{"value":"bipartite metrics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842652$F97CA857-395C-4FBC-A326-F1CDB6E42716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842652$AABD4C42-E48E-4EBC-926D-254A1471102A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cc368e3db50c98d6dbe7e70c58f215b9063f9066","datavalue":{"value":{"entity-type":"item","numeric-id":1406029,"id":"Q1406029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$4F0569B5-D301-4878-9AD6-1948361D93DF","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":"Q1842652$A3069C9A-212B-48F0-B4D5-B4CF933C0CB4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"511cf7456981908a57e5b812c29baa8a35c2230f","datavalue":{"value":{"entity-type":"item","numeric-id":3915007,"id":"Q3915007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$42D98804-1D80-4247-9FDF-1C2C859BE6A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecdc3660d18fb05db4bae70284c5481a09afd760","datavalue":{"value":{"entity-type":"item","numeric-id":3934399,"id":"Q3934399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$165D1099-5955-473E-A4BD-FB4629842EFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05a76cc8213cfb3955e3d4feab85af42779246b0","datavalue":{"value":{"entity-type":"item","numeric-id":3984283,"id":"Q3984283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$00AC2522-06E4-4BFD-AEBA-073C480D3F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e2eb6ab26cbc8485f27150c09d620cf79d9285a","datavalue":{"value":{"entity-type":"item","numeric-id":3892263,"id":"Q3892263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$2BAFEC0D-10E4-41F1-8EC1-2597F0A6A39E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34dc28351f84be76c1393cd5104a4fffd76ddb72","datavalue":{"value":{"entity-type":"item","numeric-id":758950,"id":"Q758950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$DCC260DB-6778-48E9-BA9D-5790EE72DF7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c52adfebc0a3f980b3432b402cefbae9d237a169","datavalue":{"value":{"entity-type":"item","numeric-id":3336286,"id":"Q3336286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$52F8623A-CEE0-4D40-9998-77E80AE3EDA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c424f9fdfe9b2b300cf7717a2043d99ead6fd495","datavalue":{"value":{"entity-type":"item","numeric-id":4193465,"id":"Q4193465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$F78AE572-CDB2-4E74-B4C4-A87C6B1D8DF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8073ee9d2a965d5f27237bf6fc5a1d954f7a7c7","datavalue":{"value":{"entity-type":"item","numeric-id":1199749,"id":"Q1199749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$9358F8DA-52C9-4B6F-901A-4C30CAB828DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2436afecea717d449f669935f2d48c064b2aa71","datavalue":{"value":{"entity-type":"item","numeric-id":2555084,"id":"Q2555084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$50C9C638-A2EB-4DE8-A7E1-0E0AA8E7F926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e258e2c5ea92e62da411b83c824d05565b8b4b11","datavalue":{"value":{"entity-type":"item","numeric-id":3680585,"id":"Q3680585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$B4872914-ED61-4958-96F2-D83FDB57F879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ec094bc44d17139c878f031290f64c86ee6e771","datavalue":{"value":{"entity-type":"item","numeric-id":4320817,"id":"Q4320817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842652$5056D523-92DA-4A71-A650-CFAA1A8F4130","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ebf75f2336a2585b8cf6d8ea8b50c713dddaa005","datavalue":{"value":"https://doi.org/10.1016/0166-218x(94)00087-t","type":"string"},"datatype":"url"},"type":"statement","id":"Q1842652$3538B0C8-FF84-40D7-81F8-174448409A55","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"233f95a99571f5f192ae3e0d43e871a6752a7dac","datavalue":{"value":"W2072192166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842652$CFA6C705-BCBF-464C-BAEC-75541BC0C7C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dffd615596c3dba7f30f2176e36ff5fba2611df","datavalue":{"value":{"entity-type":"item","numeric-id":1110526,"id":"Q1110526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06c461c0ce9d5f2b490eeb1c54d7947d5d57490e","datavalue":{"value":{"amount":"+0.7711970806121826","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":"Q1842652$7DCD3B3B-AC1E-45AD-9FB2-46B78E1EDF10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"281bc9d3e0b714595fb4661133f8d499987d5714","datavalue":{"value":{"entity-type":"item","numeric-id":1089359,"id":"Q1089359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0eb428070a67555745151abb2380880ac52d69cf","datavalue":{"value":{"amount":"+0.7698960304260254","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":"Q1842652$1DE24E7B-567E-4232-9E26-2C707DEE2844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a59568ac286f12278087eb4b2393388e7d246e1d","datavalue":{"value":{"entity-type":"item","numeric-id":2397500,"id":"Q2397500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deb4f9c3516b3c82cfcd680cce3ac66ae2d21a8f","datavalue":{"value":{"amount":"+0.7626927495002747","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":"Q1842652$808183B7-76AF-4419-A345-6C209508A393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63000a5893411f8c20447e34707e14b5c00a3749","datavalue":{"value":{"entity-type":"item","numeric-id":3685588,"id":"Q3685588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c715cf5bc1c9991afa847c25ba5b7700c3562f37","datavalue":{"value":{"amount":"+0.756727933883667","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":"Q1842652$A646BDD8-03A0-42A0-81FF-5DF4EEEB6C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bf67e73b04079b78d08f5d75dbed10ce80fe71e","datavalue":{"value":{"entity-type":"item","numeric-id":4894976,"id":"Q4894976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f580b49fd2f44c065670e9c888c9174587dbb91","datavalue":{"value":{"amount":"+0.7557986378669739","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":"Q1842652$B417A402-3EA2-48AC-BFFB-5C8E0997D475","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hypercube embedding of generalized bipartite metrics","badges":[]}}}}}