{"entities":{"Q4268880":{"pageid":6298481,"ns":120,"title":"Item:Q4268880","lastrevid":46782417,"modified":"2025-12-25T14:14:48Z","type":"item","id":"Q4268880","labels":{"en":{"language":"en","value":"Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\\cal NP$-Complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1354518"}},"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":"Q4268880$A95891F8-6C52-4F37-9620-A686120BC875","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4ae4506d32b580c1483645795ae676a8a521f170","datavalue":{"value":{"text":"Routing with Minimum Wire Length in the Dogleg-Free Manhattan Model is $\\cal NP$-Complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4268880$6A53F22C-833C-4A73-86F1-6F2C01604731","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"72c6c850710bd515f0e25d5cbcdbc78820b3cd02","datavalue":{"value":"0937.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4268880$9C10A0C6-0AC6-41C2-A36E-DB8D8C0BA47A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"279b6b66bde4b5dc82b7a1bbebf61ac88d3cd1da","datavalue":{"value":"10.1137/S0097539796303123","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4268880$746B9CAB-290F-4A65-9924-92A660561CD8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a13d1645d1f79c21fba02f0997fe0e319af6be83","datavalue":{"value":{"entity-type":"item","numeric-id":519014,"id":"Q519014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4268880$E3C7FA6B-3F05-488A-90CB-F5338CE7AA3D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4268880$FB49789B-91BC-4750-A17D-2E98B2EE3CCB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1eeeea4931e75e6b5358c627cc3e151b80b82718","datavalue":{"value":{"time":"+1999-10-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4268880$E0E9E814-4CE1-4688-B2E1-CF5A123825A0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4268880$2994AB13-B019-41E4-A788-778D00DC657C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3cb322112ae56aec500b334b7351f32fb107365","datavalue":{"value":"68W35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4268880$27EE69D8-5D28-410D-B64E-949B7CA82F21","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8e2a78481121af4be424cdc6edf3e6808bc0ed2a","datavalue":{"value":"1354518","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4268880$50CA3DED-7B1D-45D0-86AB-EA8B73C0C081","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b171024e7e566dccad476d548aca4aa09a7bd58a","datavalue":{"value":"single row routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q4268880$3E4B517D-F7B7-48CD-8C83-07586D2A3291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c4df5c0cd246319ec98364cc18f750639d6c6e1","datavalue":{"value":"VLSI","type":"string"},"datatype":"string"},"type":"statement","id":"Q4268880$10CD2E90-324C-44CE-841A-7B6F08ED7134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba9256166f08c57cf2c6534911b18e7e2f3236c1","datavalue":{"value":"\\(\\mathcal NP\\)-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q4268880$8D1D1C37-2761-441A-ABA6-F391B4A6530A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a09201a0cd953c835e0c00de6122202a55ced15","datavalue":{"value":"minimum wire length","type":"string"},"datatype":"string"},"type":"statement","id":"Q4268880$731796A8-6A43-4355-ACC7-B4B7C38C0C6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a949c568749d2f4337e1772be827516d5211abc","datavalue":{"value":"interval graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q4268880$A68E8902-EB7B-459E-985C-4B8552D97676","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":"Q4268880$874B2731-B036-4BC7-B36C-B44781E26F48","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"504a5bf61c137136cf3c33314f6f3d57c5eb1c9e","datavalue":{"value":{"entity-type":"item","numeric-id":4259980,"id":"Q4259980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfd3a4d16201896da700ca1d57f3b914fe20c1ee","datavalue":{"value":{"amount":"+0.7988564968109131","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":"Q4268880$7D798BA4-ACB1-4973-AA9D-410855D115C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c35610e491a7dbfc211b7118aa550e6f895d922a","datavalue":{"value":{"entity-type":"item","numeric-id":1209358,"id":"Q1209358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c21d89b476585bc6bfde80a41ba68cfcc3bde814","datavalue":{"value":{"amount":"+0.7845785021781921","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":"Q4268880$266C56EE-5411-4894-ACF7-68A4EC37DE20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dcd96b8d9780c3f37295f73daa39a02e9c133d7","datavalue":{"value":{"entity-type":"item","numeric-id":3684052,"id":"Q3684052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c89e709a079e1953c2051b4caaa735f9050e294","datavalue":{"value":{"amount":"+0.7617012858390808","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":"Q4268880$CBB7F4DB-D529-4E1C-97C6-E772200F02E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85a3d56c9da5c1ca1eceefc15b6c046b9bced38e","datavalue":{"value":{"entity-type":"item","numeric-id":4028915,"id":"Q4028915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5be0e8c61b189aa086b0bb52600deb93078a469","datavalue":{"value":{"amount":"+0.7601326704025269","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":"Q4268880$3E2225FE-D46D-48E9-93EF-40E5A8C8521B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4268880","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4268880"}}}}}