{"entities":{"Q1812948":{"pageid":1823690,"ns":120,"title":"Item:Q1812948","lastrevid":73013982,"modified":"2026-04-14T09:23:29Z","type":"item","id":"Q1812948","labels":{"en":{"language":"en","value":"Minimum-delay schedules in layered networks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1005"}},"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":"Q1812948$1976768E-36CD-46E2-83D0-5C2D754D8979","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b65712ff83281c0ea942ee7aff821883dd7ac1e","datavalue":{"value":{"text":"Minimum-delay schedules in layered networks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1812948$EE8A9D78-71CE-4AA7-B360-93718E5DA248","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d2ebe8553d0e0cad5558f35eb8f8a79f0c7fe708","datavalue":{"value":"0706.68015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1812948$DCC3DC49-65F6-49B6-8222-C3E43C7B3130","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c46c28d0acee3357e1be182ed6e255852d749675","datavalue":{"value":"10.1007/BF01178583","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1812948$F94BC770-9C22-429F-8A8B-A031FF94F3DF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2cfe6cd4b6f96e92f55b16a55e8d306d4caaa140","datavalue":{"value":{"entity-type":"item","numeric-id":1106216,"id":"Q1106216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1812948$AAB07EE1-CBD5-4026-90C9-BB13D503FFF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"91d50cdeb23e4905b247ff213c2d9fe1cf6c555a","datavalue":{"value":{"entity-type":"item","numeric-id":222483,"id":"Q222483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1812948$E4CBDD9D-194C-4CEF-9E7F-BCAC9117BD0E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1812948$58EF3C7E-7989-44E2-A866-A8050D96A2E1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1812948$802BA72F-7780-46D7-B0C9-1F228511117D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"288115f712e3a3f25c156a439b80c2b99fd09c63","datavalue":{"value":"We consider the following problem: Given a layered network including a set of messages, each of which must be transmitted from a source to a sink node, what is the sequence of moves from one node to another which minimizes the total completion time? We first show that the general problem is NP-complete for both fixed and variable path routing (thus the scheduling problem for more realistic networks with cycles must be considered computationally intractable). We then consider several restrictions which admit polynomial time algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1812948$60B4CFED-932E-48BF-8493-1F161EE8705E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca8c16691e9ec83d46a3995338b09d48ac9660ac","datavalue":{"value":"68M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1812948$3E8DCC42-1B6E-41D8-BAD5-D1AC384CF76B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1812948$C57C1EB0-BBFD-4B2A-8123-1F2828C6FFA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1812948$C9DFE7F8-30CD-4E1E-808A-1E995EB3AD14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1812948$53B73D5E-00F3-442D-86F8-2FC1AC553D44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6ce1093a247be3a8b3780005738fa424acd6c05c","datavalue":{"value":"1005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1812948$D051FA8E-9DB0-4C2C-9245-21268D4AD114","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c48b023bd500fa328b355b186bd15b46dba56c13","datavalue":{"value":"layered network","type":"string"},"datatype":"string"},"type":"statement","id":"Q1812948$4C0B0AB9-FAED-456C-9A13-328FD5A164A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be9847b5080561732e2df3fe2a5afade2166808c","datavalue":{"value":"routing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1812948$BF263B1C-8F51-4882-8D7E-0C61B186B0AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8752778762fa3edafed355943372c23aa3910498","datavalue":{"value":"scheduling problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1812948$166A1F0F-5987-4A98-A02E-BDE807014176","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":"Q1812948$46CD3DB4-F7E0-412A-B7B4-273AE5435445","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9661dc321e9197c44616cc21a898b0798188a31","datavalue":{"value":{"entity-type":"item","numeric-id":4131987,"id":"Q4131987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1812948$A8D93721-7980-4217-A29C-B0CE2EEB0E1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fae306fb5b216ca7a979cf42513dbb739d5ef6cf","datavalue":{"value":{"entity-type":"item","numeric-id":3741046,"id":"Q3741046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1812948$B9329D3B-5AE6-4C29-BF27-39589CD37315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1812948$6DF6E9FC-816F-4329-A62E-EC04A1788A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"102773d10765ac7344d721acbb33968c8260163f","datavalue":{"value":{"entity-type":"item","numeric-id":1153123,"id":"Q1153123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1812948$EDF93D43-2B39-4A7B-9D44-541371FB763E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23a6815109b9dcafe384dbac2193ef0366049adc","datavalue":{"value":{"entity-type":"item","numeric-id":4853335,"id":"Q4853335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42312de38eb3d9b57ccd08dd84cffb97f64ef4e8","datavalue":{"value":{"amount":"+0.8269690871238708","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":"Q1812948$9DB46D0A-669A-4105-A793-E5A1B5E4D4DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2375ed9b6ef32816b24a0ae8d613cf0e68871203","datavalue":{"value":{"entity-type":"item","numeric-id":3696506,"id":"Q3696506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c16e0c412fa86e02c2dc22f1f51724b0bd8d0781","datavalue":{"value":{"amount":"+0.8203248977661133","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":"Q1812948$92FC34D8-E79D-416E-9FB6-4C8496AFB6EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83e3a5dccc4412b484711d0d8d1cd9e520eb3028","datavalue":{"value":{"entity-type":"item","numeric-id":4254351,"id":"Q4254351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d12d34e0ec1cc8f671cf54cab37e9e7dabca3ba8","datavalue":{"value":{"amount":"+0.818621039390564","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":"Q1812948$337642F6-C8FA-409D-A5A5-FD69A2A3547A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab25392e1f4806e66e1c30bd3838958fc06ed3a8","datavalue":{"value":{"entity-type":"item","numeric-id":4017614,"id":"Q4017614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2571e5d5e710787d9501a8bf8e7a76c4103cd316","datavalue":{"value":{"amount":"+0.798408567905426","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":"Q1812948$4AFB512F-B24F-4914-82A4-87A293F8F81B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum-delay schedules in layered networks","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum-delay_schedules_in_layered_networks"}}}}}