{"entities":{"Q3677185":{"pageid":5707091,"ns":120,"title":"Item:Q3677185","lastrevid":88884554,"modified":"2026-06-04T15:44:19Z","type":"item","id":"Q3677185","labels":{"en":{"language":"en","value":"NP-completeness for minimizing maximum edge length in grid embeddings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3898254"}},"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":"Q3677185$1AF13C32-6BD0-4930-A708-4CCE6DB30D99","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc7e362acba055820517b5dc4e4fa339dd6b0fec","datavalue":{"value":{"text":"NP-completeness for minimizing maximum edge length in grid embeddings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3677185$3D88DCB7-BD56-4709-9AF2-A821C3B00761","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6c9288f40a2ce040aa28cd398af31e81eeaf7672","datavalue":{"value":"0563.68058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3677185$A48E12C9-2F4F-48AA-89A0-9CDB40D4FDF0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"22ee77da06a7c20ec43b8ed0fd03fa4c928d7c3c","datavalue":{"value":"10.1016/0196-6774(85)90016-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3677185$4B8A3453-4911-4CAC-B966-ABCF41F6BD80","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9bcfebe9d23b7752651008b0d843e08ec7c57a37","datavalue":{"value":{"entity-type":"item","numeric-id":2709787,"id":"Q2709787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3677185$EC65E77F-8D95-4117-AE69-14F707227AB7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q3677185$695A8A87-C2AF-4C0C-A3F1-E574F26BE778","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3677185$47710654-C789-4ECE-BC53-5FC165CC5CB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3677185$B1FB31BD-098E-490F-833F-2795193174C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3677185$887FB676-83E0-4B86-A997-8F2945E1DDA6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b7449fd5c2d61a5f61648264ccf67dbfcbf51b4c","datavalue":{"value":"3898254","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3677185$536CD415-D419-4FD3-B8CB-DA7178A05587","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q3677185$5340AE6D-FF15-418F-93A1-4133C7924040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb6f1baff13cdf595fcb305c4ff855a183d79876","datavalue":{"value":"graph embeddings","type":"string"},"datatype":"string"},"type":"statement","id":"Q3677185$C9088641-8DB0-4E26-9ED7-B025303BB85C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"353ebf478ec3562017881f4fdcd88a57e9220966","datavalue":{"value":"two-dimensional lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q3677185$5D160C31-FE0A-4477-84E1-3DF71AA6B944","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6a26fefc06ca79d5220794da5d11e2469df74786","datavalue":{"value":"Q59592734","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3677185$E4952A47-532F-43FE-A6AC-646AB7183872","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":"Q3677185$C131A0FA-D3A3-4AA7-9126-213923031A25","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"24666de08a583819e9a6dab11b882102f675bba5","datavalue":{"value":"https://doi.org/10.1016/0196-6774(85)90016-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q3677185$E8E0558D-953B-4875-A3DB-BFFEA07D475A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"358ded1a9c73a342681b09aa8372831d223a554a","datavalue":{"value":"W2117771589","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3677185$91A8628B-911D-4A34-B1D7-669B1DEA743F","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"3c190dd957ec16a29205a2e1fca9e20b65f18b5f","datavalue":{"value":"journals/jal/MillerO85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3677185$718B75A4-38FC-4A4D-B71C-BE4444E82331","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dc6a607e6378c103370cc2a132a050bee6e5d73","datavalue":{"value":{"entity-type":"item","numeric-id":2629266,"id":"Q2629266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26584890ccfab704785ad8bf4bb0c1a695bf3e9d","datavalue":{"value":{"amount":"+0.8758932","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$82D1B4D0-10EB-4E4C-A5C0-4EE7F85E9736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aac9575b2dc28645f6d6b61feeb09878fc9cf8b8","datavalue":{"value":{"entity-type":"item","numeric-id":765326,"id":"Q765326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5989de344d9fea67a7b7b01604c84845cbc7db4","datavalue":{"value":{"amount":"+0.87582767","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$DBD54A77-0403-4A3E-8C6B-E4C8D432EDB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90d988c4260810bf76fc94719b273e2d4bcff942","datavalue":{"value":{"entity-type":"item","numeric-id":719276,"id":"Q719276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18428a03e6223347b83ce92dbb5ad42f5d1bdaea","datavalue":{"value":{"amount":"+0.8720133","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$6C449951-D226-432F-BF80-2E14C4355527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee6779d69fd313c36649d482f67bb6c404119eb8","datavalue":{"value":{"entity-type":"item","numeric-id":3801098,"id":"Q3801098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63f68c54cdec315ba3dac841c6a61641b139fedb","datavalue":{"value":{"amount":"+0.8692811","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$81348B49-D88C-4D1D-8102-99DC6E5FAD95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"202dbb63d4259189e779d59c5d5113422c6382a2","datavalue":{"value":{"entity-type":"item","numeric-id":5426011,"id":"Q5426011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d54cf046a02c7971cd741321fee1f0dc72598c8d","datavalue":{"value":{"amount":"+0.8682272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$93663FDF-2F37-4E87-AB5D-7BFCA6C7ED1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d16473bcc1afbbde81414b29fb8cbf6958343238","datavalue":{"value":{"entity-type":"item","numeric-id":2272195,"id":"Q2272195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63d4daec647e3eecba2f782f7473300584af83a4","datavalue":{"value":{"amount":"+0.86822706","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$5866E574-8F9D-4138-9875-6E9211B41C16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e57f937752e812bedccdbbd1e5e37924db3ff2eb","datavalue":{"value":{"entity-type":"item","numeric-id":2500532,"id":"Q2500532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd9b39b4b95a243a1198f772b687aeb8dd784902","datavalue":{"value":{"amount":"+0.86747456","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$1C354155-808D-40DF-A1B4-1B57DB364409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6091453e4a24ac62ce68689db99ed1dba2c687af","datavalue":{"value":{"entity-type":"item","numeric-id":2014718,"id":"Q2014718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7244391110e303b99c4d3b7228eeec1532ee1ec6","datavalue":{"value":{"amount":"+0.866994","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$0EE98931-37A4-4E84-A2DD-306BC148EF8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"797d2b9e36fec50072dc0431dfc2a80bdc3916f9","datavalue":{"value":{"entity-type":"item","numeric-id":1687922,"id":"Q1687922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d67bc6f6b13673cc199f9d3baac162c39fb205ab","datavalue":{"value":{"amount":"+0.86662924","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$A3B717B6-F479-4ABB-BDCE-B180AB668201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5514482beca819dd01eaf1ef9b178c4668647a70","datavalue":{"value":{"entity-type":"item","numeric-id":5232522,"id":"Q5232522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1d9038fb74bd3e21ee35e6235b06af465666c9a","datavalue":{"value":{"amount":"+0.8609336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q3677185$F4EACE1A-2209-4484-AB3B-0BC629C171DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"NP-completeness for minimizing maximum edge length in grid embeddings","badges":[]}}}}}