{"entities":{"Q908701":{"pageid":910549,"ns":120,"title":"Item:Q908701","lastrevid":65267967,"modified":"2026-04-12T01:25:43Z","type":"item","id":"Q908701","labels":{"en":{"language":"en","value":"An optimal time bound for oblivious routing"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4135401"}},"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":"Q908701$9856655E-C0EC-40F0-A8D0-B95600B5C3AA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fc2a5c43b84ca3b208808c76af0debd8ab2c5f66","datavalue":{"value":{"text":"An optimal time bound for oblivious routing","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q908701$1A1633DF-CF66-4137-9048-3D107DD3E4BF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"65e2fbb966da305113926d8495f51d7bcbd49858","datavalue":{"value":"0693.68028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908701$ED454464-7575-408D-9575-D81ADF72BFAA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9679e612ee36480df2f8342fb18341b3278db0f3","datavalue":{"value":"10.1007/BF01840387","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908701$C4696D84-C31B-406A-B247-75DE591CC6A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7712420576ab073f1af3f431c71f5fc7fbb67a0d","datavalue":{"value":{"entity-type":"item","numeric-id":582118,"id":"Q582118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$B6475A43-5FDD-408E-A7BF-749EB158CE4A","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":"Q908701$5214014F-2EC7-4579-96B2-56679D6115B1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q908701$40F6F5C8-ABD8-4D7C-97A1-E402B7D6AC0C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5b19c0af4641cc8df1b5f0c4a8411fbf4aafebe7","datavalue":{"value":"The routing problem is the problem of routing n data packets in a network of n processors. Usually, such a network is assumed to be constant- degree, i.e. each processor is connected to a constant number of other processors. A routing scheme is oblivious if the route taken by each packet depends only on its source and destination. Previous results by Borodin, Hopcroft and Lang show that oblivious routing can be done optimally in \\(\\theta\\) (\\(\\sqrt{n})\\) time. The author considers the case when more than n processors are available; more precisely, he shows that if p processors are available, then oblivious routing can be done in \\(\\theta\\) (n/\\(\\sqrt{p}+\\log n)\\) time. Applications of these results are also given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q908701$9C850214-67B9-4F7F-B5B2-4DFCF4277BB0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908701$DD421B37-5A2A-4C50-836A-4C3BE81F2766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"517ace4a4f9c45a5475b4a8927a567447dbdb293","datavalue":{"value":"68N99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908701$3CC4A35A-1336-4A6A-841B-8F152EF47FEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908701$892BC818-B907-44B5-80BB-2765A1CBE1AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908701$118DDF37-CF81-4144-B7CA-D36D4885748A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"70b245781f6fde9cb58541f7e6d24ae660db0fc7","datavalue":{"value":"4135401","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q908701$20E27F63-0104-4215-8ABD-53079CD809AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94fd702374821773c81889c4ec64bfc7707ff772","datavalue":{"value":"network of processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q908701$D0E29A7E-5F00-4CB4-914C-C117E7F66062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f3dacb73fa9efa57cb94c5b919ad076d0f9817dd","datavalue":{"value":"parallel machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q908701$1B634071-A3B5-4B99-87FB-701BBD8A77BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4a91d1e335b10fa8fd905339afad015efc1ec1a","datavalue":{"value":"shuffle-exchange","type":"string"},"datatype":"string"},"type":"statement","id":"Q908701$0F16789C-3BCD-49F7-98F7-C28DBDE8DC8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e82885cbe5a0dc126c7ec7a3caca584177b90d0a","datavalue":{"value":"oblivious routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q908701$7E1DE0D0-1074-4126-8D97-DA3266C7C65D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$B6B05FA8-D341-41DF-9A65-26F3CB2CB0DC","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":"Q908701$46134213-9C06-4C70-8876-75802BF59BEC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2bd35d34c8cb4660ca6ae9b0c6b460814b14576","datavalue":{"value":{"entity-type":"item","numeric-id":1082818,"id":"Q1082818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$5C18DA6F-39C0-457E-985E-C8CD4A6AF854","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07adfa7411d8716c42e7a81a35a8dc21f533009d","datavalue":{"value":{"entity-type":"item","numeric-id":3951543,"id":"Q3951543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$19A68865-10E8-45D5-9789-8CCAB2D35ECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a3e6af5fd8fe82f2e79319ebdb8bdc9fb84cba5","datavalue":{"value":{"entity-type":"item","numeric-id":4088287,"id":"Q4088287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$0411BF98-EFBC-4E84-877A-7A5EC9C74723","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"662fddc70a56ae9912f6b9a3b75429dc263f09ed","datavalue":{"value":{"entity-type":"item","numeric-id":3949979,"id":"Q3949979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$225EFEB5-FD4A-458E-80E9-DA23B061E7D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd3b9caf56c0a645423fbed55fc5a04a544b398b","datavalue":{"value":{"entity-type":"item","numeric-id":1077935,"id":"Q1077935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$590635A9-22F7-498F-96AC-B17634A34E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9eb8e5a54f3467be8354347b79423c57b2b1ff6a","datavalue":{"value":{"entity-type":"item","numeric-id":3801042,"id":"Q3801042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$7D1FD55D-064D-46EB-BF7E-06AF575AA2F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88ee2caf0b429126bd09e676e925d96386bd9266","datavalue":{"value":{"entity-type":"item","numeric-id":1100882,"id":"Q1100882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$055CDA0E-EF19-42A9-A290-49EF721D2C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38b3c07b155ac762465b61e25773bda60a652f62","datavalue":{"value":{"entity-type":"item","numeric-id":5617294,"id":"Q5617294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$59FB35D0-712B-4497-8B19-985068D4C968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d1d1cb66d27d2e53aba37392ad47b61e11f859","datavalue":{"value":{"entity-type":"item","numeric-id":3326832,"id":"Q3326832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q908701$F5A0679E-2FB2-421A-9A3B-924F10FF010D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b681e56eff8c4bd4026f9d372b0de1be411c6b8","datavalue":{"value":{"entity-type":"item","numeric-id":1770370,"id":"Q1770370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5eccc097b9ca9374fcb33b0f1fd9ee32ad348e13","datavalue":{"value":{"amount":"+0.8560998439788818","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":"Q908701$3A40F83D-9A6A-4EFA-BC38-338B536B61F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6218952e22eef1ae19357556d96f074fd63e8f5","datavalue":{"value":{"entity-type":"item","numeric-id":3357537,"id":"Q3357537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"798df2434138bbd423913078334d9c2c94e4ddd7","datavalue":{"value":{"amount":"+0.8550646305084229","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":"Q908701$29C46511-38EA-4204-9D0C-41191A6A2B19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f64d5c36540fa469b13ca3d43e651b6c4ce0e9a","datavalue":{"value":{"entity-type":"item","numeric-id":1176105,"id":"Q1176105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd9947365cbeee7ed48ba01ad153c38d2e11df51","datavalue":{"value":{"amount":"+0.8357464671134949","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":"Q908701$DFEB818E-E145-4FF2-91F7-628F329D35C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85431a2ed6e3964e0aad1d0679250c664f96be7e","datavalue":{"value":{"entity-type":"item","numeric-id":5917575,"id":"Q5917575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab2e6ecfb3d2634edcebdcbdc58822ed94457a22","datavalue":{"value":{"amount":"+0.8332421779632568","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":"Q908701$5A7765CF-2B9A-41B8-A95C-6952CD0437E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1e44c3f01275c05e11c7009ed74193be8613b09","datavalue":{"value":{"entity-type":"item","numeric-id":3468611,"id":"Q3468611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"184512b11717d99ced93bfa335a127eddea51534","datavalue":{"value":{"amount":"+0.8316288590431213","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":"Q908701$7965543A-8E10-4473-BCA5-8F153786A56B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimal time bound for oblivious routing","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_optimal_time_bound_for_oblivious_routing"}}}}}