{"entities":{"Q802877":{"pageid":804725,"ns":120,"title":"Item:Q802877","lastrevid":49496059,"modified":"2026-01-07T07:55:47Z","type":"item","id":"Q802877","labels":{"en":{"language":"en","value":"Optimal algorithms for adjacent side routing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4199640"}},"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":"Q802877$BC0F6BED-E088-47A1-BF95-9E769FADE311","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"feec7f456c40f1541a9f9da64466ad4475c9ccbc","datavalue":{"value":{"text":"Optimal algorithms for adjacent side routing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q802877$85CC5C3D-7CC4-40F5-AA00-0976DF51199F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9b4de31b20cf193e6296c8364638ba7a3e874a11","datavalue":{"value":"0726.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802877$521CF2BF-F789-4880-80AF-A760FB601FE3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7611162607ce5584f443ff074590af25d03ac2df","datavalue":{"value":"10.1007/BF01759060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802877$63E9720A-40D4-449D-B6AE-F4482D06EE11","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"18da68c58711ef4ee8fc3b1c0149f1c0f5f493d1","datavalue":{"value":{"entity-type":"item","numeric-id":802875,"id":"Q802875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802877$50C24D82-5396-48B1-BCB5-7102B3A9364D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd51aec820ad81546fe69975eab1ae2dbb826f71","datavalue":{"value":{"entity-type":"item","numeric-id":1365678,"id":"Q1365678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802877$AA4067C0-ABC5-4AE3-9D8F-B46E05B1A869","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802877$86DD62F4-538F-44A9-BEB3-23DE9345583E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q802877$F098282E-4924-45EB-92FC-0958561FE307","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a58246a20a29dd0d175181e249afaacd2349b33","datavalue":{"value":"We consider the switchbox routing problem of two-terminal nets in the case when all the k nets lie on two adjacent sides of the rectangle. Our routing model is the standard two-layer model. We develop an optimal algorithm that routes all the nets whenever a routing exists. The routing obtained uses the fewest possible number of vias. A more general version of this problem (adjacent staircase) is also optimally solved.","type":"string"},"datatype":"string"},"type":"statement","id":"Q802877$3EB812A4-1D23-4F40-9E84-73642953D87B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3cb322112ae56aec500b334b7351f32fb107365","datavalue":{"value":"68W35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802877$08FBC1B2-F938-48A8-92F8-2A35836EEAE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802877$E7589AA0-58E0-499A-B7D5-D49449BD2010","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"09174f6db6530cbbae2df8da2ecdc3cf9af053f7","datavalue":{"value":"4199640","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802877$D00DA711-35E2-4F39-8A06-0A9A8B5C21D1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0f8d16a027dc58206cf062fd625c6f35e5b1370","datavalue":{"value":"VLSI routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q802877$6C491945-6042-41AB-89FA-97CC4B12D031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"025f53735aafc56ba6d13e7e11c0c37109869dbf","datavalue":{"value":"switchbox routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q802877$E0A9050E-BEA0-4EAD-8233-5C1FCDD5A3AA","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"d6e0df85abc74951171f116923dc78077aa7d836","datavalue":{"value":{"entity-type":"item","numeric-id":22779,"id":"Q22779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802877$8F8A6AF9-7895-4384-9915-67D637B5C11C","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":"Q802877$A7A4E48F-6149-416A-A3FD-6BB24F244FD0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fdc1b1213cadf6ec10af2b6b120336877933090","datavalue":{"value":{"entity-type":"item","numeric-id":3684051,"id":"Q3684051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802877$BB692BAF-7105-4440-AC3B-311E2A4DE18C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a1374d79c4e09a6ec584a7823d31e5f63a457ca6","datavalue":{"value":"https://doi.org/10.1007/bf01759060","type":"string"},"datatype":"url"},"type":"statement","id":"Q802877$F8EBBAC1-0E72-41D3-A945-84E8FD689629","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5e7825967e196c9fe05023a26ce461693e497c06","datavalue":{"value":"W2053848761","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802877$1602A892-9D3F-4D42-B737-EBCC19E64939","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2356911d17a5c1e5ce99529ec778779d79732a6","datavalue":{"value":{"entity-type":"item","numeric-id":3707923,"id":"Q3707923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e440fc4526fcaadbfe5331b14f29cf304f625d8","datavalue":{"value":{"amount":"+0.8390976190567017","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":"Q802877$75DB8A45-17C9-4F94-B35F-7D16139087A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7819723c15b88fef4a432520b30eee6cd9433ddd","datavalue":{"value":{"entity-type":"item","numeric-id":3768418,"id":"Q3768418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8865444e7bf3845d853fe1d44dff0184f46de398","datavalue":{"value":{"amount":"+0.836018979549408","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":"Q802877$225326FF-6D66-4489-AAB1-23A3CCF7797C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04bab95cf6465f2933ae7526efa93409ee079143","datavalue":{"value":{"entity-type":"item","numeric-id":3753505,"id":"Q3753505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3bcb3ee15f72922c72ca9f04a2638790d8cdabb","datavalue":{"value":{"amount":"+0.8105063438415527","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":"Q802877$747D6950-44BB-4D00-AC7F-F32A88CFF268","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8aeafefd8aa2a81271c0db6947e94999af45079","datavalue":{"value":{"entity-type":"item","numeric-id":3816979,"id":"Q3816979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38ce30d2139f573deacafd507eb3ed660aaac68b","datavalue":{"value":{"amount":"+0.809715211391449","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":"Q802877$62205A0E-D446-406A-9E07-D4CBBEAFD8D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8906aff588c330486fc6c0b2f7464bfc9a92f5f","datavalue":{"value":{"entity-type":"item","numeric-id":1208452,"id":"Q1208452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74596b8bcae3d255ec7d4a294c91084035c80094","datavalue":{"value":{"amount":"+0.8065855503082275","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":"Q802877$0B14BAAF-2A76-4FD1-9EBA-F0C0D95D5FB4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:802877","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:802877"}}}}}