{"entities":{"Q1329794":{"pageid":1340544,"ns":120,"title":"Item:Q1329794","lastrevid":68843178,"modified":"2026-04-13T02:26:15Z","type":"item","id":"Q1329794","labels":{"en":{"language":"en","value":"Faster isometric embedding in products of complete graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 612419"}},"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":"Q1329794$910C2636-9D41-455C-9F95-C47A82902013","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"14efb45aef91d8606e27ec9b8c038e106042c57d","datavalue":{"value":{"text":"Faster isometric embedding in products of complete graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1329794$48041235-7DA1-42A7-A896-256ABB56BA80","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"81349ecff53b21ca0b86ccc9b330684b15ecb1da","datavalue":{"value":"0808.05086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329794$949A9756-E795-463F-9FA9-FF882EE05300","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5acf096e9f81e67a40769c9659893058c5b0cb9d","datavalue":{"value":"10.1016/0166-218X(94)90154-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329794$3CBC6C19-A7CD-447C-BD5A-7177510B44D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"24d2f620d2974ebdd1015229debd06431f4c7398","datavalue":{"value":{"entity-type":"item","numeric-id":1294575,"id":"Q1294575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329794$3A4B6FCC-E452-4AC7-BBFB-4B6EAA6EB532","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":"Q1329794$B7DD45CB-1541-4A86-8ADF-E1EBA53D6D49","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eac7e87cda3f5ebbd31cca085641373723d63407","datavalue":{"value":{"time":"+1995-03-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1329794$5512A4E2-397D-4AE0-B371-C7F07D5459BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a578fd682740ff979e53fc61baab7de9d50c8624","datavalue":{"value":"The authors provide an algorithm to give an isometric embedding of a connected graph into a product of complete graphs or to ascertain that such an embedding does not exist. If the distance matrix of all pairs of a graph with \\(m\\) edges and \\(n\\) vertices is part of the input, the algorithm runs in \\(O (n^ 2)\\) time. Otherwise, the order is \\(n^ 2 + D (m, n)\\), where this latter term is the time to compute the all-pairs distance matrix of a graph with \\(m\\) edges and \\(n\\) vertices.   The paper also shows that an \\(n\\)-vertex subgraph of the cartesian product of \\(d\\) cliques of size \\(a\\) cannot have more than \\((1/2) (a-1) n \\log_ a n\\) edges. With this result, the algorithm can decide if a graph \\(G\\) isn an \\(a\\)-ary Hamming graph in \\(O (n^ 2 \\log n)\\) time, for fixed \\(a\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329794$9F85F9B0-7EC9-4A08-8A85-A533112BE543","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"61cf9dfec5b66ba829a3bd08d983df202add1f13","datavalue":{"value":{"entity-type":"item","numeric-id":801083,"id":"Q801083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329794$1B0C34AE-FA12-4F85-8230-F190633DF707","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329794$BEC9D3EB-98B5-459B-8A9C-7021520372B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329794$09D51214-616E-4A2E-8008-E6E715E198DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329794$6D3EB568-9155-42FC-804F-6EE9C547AB4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329794$319B41E6-D7A3-4218-B16A-A57C6B7D0258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329794$8018B0CC-76D9-4DAD-A78D-2EB66076A708","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329794$2F3AAB12-3593-474F-A9FF-56F124D656BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4fdd4bc4b56cedb7193a8de03a95b648990692aa","datavalue":{"value":"612419","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329794$4E9B788F-41EE-4F3B-BADF-0EC44CE6B753","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0f521aa39ae557111ec88647c9f5f9555860eac","datavalue":{"value":"isometric embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329794$8CDBC2C0-35C5-4FDE-B642-0E9F5DB1C45C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e82acb87aed14c74f2caedc7a2342baa9984d3f","datavalue":{"value":"product of complete graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329794$D6E7950A-317F-4DC7-A17E-98B73B346B6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5bd2d2f13a5fb0b02cf6f3b09d26eb080d5ff148","datavalue":{"value":"Hamming graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329794$63D0168D-6172-4E0B-9AB4-B844302088E3","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":"Q1329794$44A5FAB1-932A-42FC-89FC-A60110B88525","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"916c78bd8a9f067b63156f367131d2b8139a669f","datavalue":{"value":{"entity-type":"item","numeric-id":4028106,"id":"Q4028106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329794$686C2987-D5EE-4FB9-B5A6-DA777065851C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59945ee6409070635cac72e0a40152e769d0b5ea","datavalue":{"value":{"entity-type":"item","numeric-id":686277,"id":"Q686277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329794$D3A232EA-0F95-451C-99EC-B1DEA3414ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a42b6ad9ba92a21f931f2ead3fe79588e8a6231b","datavalue":{"value":{"entity-type":"item","numeric-id":3344238,"id":"Q3344238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329794$C26EA54B-0495-40D9-AAB8-23BDDD00A530","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3a6c7d62e6d18a5c3506f6fedc088624d640514","datavalue":{"value":{"entity-type":"item","numeric-id":4032985,"id":"Q4032985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329794$6634D612-7EA8-463D-B415-943892B55EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329794$4868AEE9-5E6A-40AC-AD60-EDA18CAD9E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e66745683a254e2edeba94d632f188e0e8c06f9","datavalue":{"value":{"entity-type":"item","numeric-id":1110526,"id":"Q1110526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329794$7C4CAE7B-E3C9-4F67-9818-3EF34FC4595B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88397f07dd795af1c91d1deee0e50c9f89cd50c1","datavalue":{"value":{"entity-type":"item","numeric-id":787171,"id":"Q787171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329794$CBE509F6-2407-45AB-9B8A-0732A81B256C","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":"ac0570d9cf2b3322fd010bf91621d47fcc90a4ee","datavalue":{"value":{"amount":"+0.8731335401535034","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":"Q1329794$60871931-DC1A-48F0-BCA1-AFAF230161D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82ff31197e230b911d0bc008cb68498341ff5629","datavalue":{"value":{"entity-type":"item","numeric-id":4309135,"id":"Q4309135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93dc71b225b1dc1caccea69fce8abe8fb54ac6f6","datavalue":{"value":{"amount":"+0.8264797925949097","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":"Q1329794$0D12D059-C0A0-4C53-9C27-B6D40028F606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d9e75c00e5f8d5ac05ba12a77f7afc2576236e3","datavalue":{"value":{"entity-type":"item","numeric-id":3697031,"id":"Q3697031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f66dddff5ce8fc63ed01ceb6f9b424c059630c52","datavalue":{"value":{"amount":"+0.7903251647949219","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":"Q1329794$8611774F-9D43-4014-930B-9984FC792EF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97f7d711599b633ba36721813ea520eaa6a2c419","datavalue":{"value":{"entity-type":"item","numeric-id":3216701,"id":"Q3216701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"942fad38e3c6eac1890fc5fa18d5991242c2504f","datavalue":{"value":{"amount":"+0.7781118750572205","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":"Q1329794$4C4B07E4-32A8-4E00-A37D-7C73C03D4FD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74ab4dcc435b000f69d4c04503921d309094da48","datavalue":{"value":{"entity-type":"item","numeric-id":3734453,"id":"Q3734453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f42a1520f8a6b49af62f487216c8295ade8f2493","datavalue":{"value":{"amount":"+0.7778319716453552","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":"Q1329794$A5513DB3-92AB-4A2E-93BA-AEBF5897BF05","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Faster isometric embedding in products of complete graphs","badges":[]}}}}}