{"entities":{"Q1260649":{"pageid":1271399,"ns":120,"title":"Item:Q1260649","lastrevid":67385313,"modified":"2026-04-12T17:16:15Z","type":"item","id":"Q1260649","labels":{"en":{"language":"en","value":"Lower bounds and efficient algorithms for multiprocessor scheduling of directed acyclic graphs with communication delays"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 370447"}},"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":"Q1260649$57558490-6362-4CD1-9399-6064E2DA7F5B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"43491688ee92a19161699ba76b251713a6639fce","datavalue":{"value":{"text":"Lower bounds and efficient algorithms for multiprocessor scheduling of directed acyclic graphs with communication delays","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1260649$44FADAA0-40B3-4184-A261-CA99672CD79A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"18e262167ae5d9ea8c424592b5a155c0491c9a92","datavalue":{"value":"0781.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260649$C0749276-42AC-4E54-B5B8-30A928AF3F51","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3bf3c97c265534ab77726e8fde8f9c1bf1122fa4","datavalue":{"value":{"entity-type":"item","numeric-id":1098630,"id":"Q1098630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260649$D55C210E-B93A-4360-8815-39F323B2DC68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3114a9e7c18fd9d37962020c44023cd148b8085d","datavalue":{"value":{"entity-type":"item","numeric-id":215098,"id":"Q215098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260649$C1A5CACA-301A-409C-855B-B0CB7813689B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d8112a4884ac488e222bb031fe5d75202a7b6dcb","datavalue":{"value":{"entity-type":"item","numeric-id":389952,"id":"Q389952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260649$1F1BD2F1-A394-45D3-867F-9069745A3653","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260649$7F4301F2-DDF7-481E-85CD-54925DCA26CC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca925aef735ee73d86c6a323015bc1282d85f7d8","datavalue":{"value":{"time":"+1993-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1260649$56960BDB-D4E6-487D-AECF-E4D062FB3DC9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c97e114e5c5941a1100734064ad8007b379ae7d9","datavalue":{"value":"The authors present an \\(n^{\\tau+1}\\) algorithm for optimally scheduling a dag of \\(n\\) nodes on a multiprocessor when the message-to-instruction ratio parameter is \\(\\tau\\). Their algorithm constructs an optimum schedule which uses at most \\(n\\) processors. They furthermore show lower bound results on the amount of recomputation needed, thus answering an open question posed by \\textit{C. H. Papadimitriou} and \\textit{M. Yannakakis}. In addition, precise lower bounds are demonstrated for the scheduling time of full binary trees. The techniques may contribute to an important new understanding of parallel scheduling when the message delay is significant, which is usually the case.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260649$3E6EFD1E-2EA8-4006-BE30-47EC17AA263B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260649$FDF00971-F821-4BBB-9160-C2092F6C082E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260649$C3387687-50D8-466D-AD74-700B4A4A6B3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260649$B81EAB2D-6FD7-4EDC-A953-21EAD3DB0A4B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cc93d9c21d4708b90681f0b738bb84d73ca4867a","datavalue":{"value":"370447","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260649$5740D9DC-2CAE-4990-BE4A-4A256BD01D08","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da5857f76acc4c6e422115b9b8c49fc730f7f62b","datavalue":{"value":"multiprocessor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260649$9E42DFD0-0D09-4634-A1D5-5AB1D7FB4349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260649$50A0EEF3-13A3-4FAE-9723-BB7F3894DB9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e362489c9d33fdd67102bad072114b4c6e59dee0","datavalue":{"value":"communication delays","type":"string"},"datatype":"string"},"type":"statement","id":"Q1260649$767C028B-6119-4BF5-8B6F-B8D81F6B6EF3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"05ba3eda7847a95b31cecabcda96410ea85a56e2","datavalue":{"value":{"entity-type":"item","numeric-id":161965,"id":"Q161965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1260649$7E5479B5-1B6E-4DC4-ABF4-2B695F6B1CEB","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":"Q1260649$1AAF44D5-2CCF-4CE4-962B-F8C863B42303","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"11e0eabc9acfe47ee00e4513f531ac377d6792d3","datavalue":{"value":"https://doi.org/10.1006/inco.1993.1041","type":"string"},"datatype":"url"},"type":"statement","id":"Q1260649$31A52CAA-8FDE-4C31-BCCE-AD94E61259E2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ecff91c4c3546e67429adf03d260b85d0f425e33","datavalue":{"value":"W1983770018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260649$B17E6912-F7D0-4E0C-9276-BB0FD03ACEA7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1cb3cd975ae174e565a8339734c82454dc359cea","datavalue":{"value":"10.1006/INCO.1993.1041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1260649$D3CB7D26-A2C7-4951-9FFA-F05C7325E5A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8991479067ea90c6ff62c2439947cd400b5958c6","datavalue":{"value":{"entity-type":"item","numeric-id":4390649,"id":"Q4390649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da6b0697b42a4d9659ef7af448a57ae17849114d","datavalue":{"value":{"amount":"+0.93908644","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260649$9DDCC1EC-06E4-4313-A0CB-8567DD11D887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fdd6aeee16172de97b0f9e14d323bed8b82a9da","datavalue":{"value":{"entity-type":"item","numeric-id":1350013,"id":"Q1350013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad516b63f60446fb222777f465fdb11f42487d2e","datavalue":{"value":{"amount":"+0.92288977","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260649$AF2BAD95-7B72-4158-8261-346A03882751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"844b78f98e44fa13c27ca3bf3ca79aaaff9bdd64","datavalue":{"value":{"entity-type":"item","numeric-id":4473911,"id":"Q4473911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ccd41de8bd6a0fa783288054204fb49251f9f4c","datavalue":{"value":{"amount":"+0.9092726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260649$2B2FCEF0-A605-4851-981D-0F1DA95D6B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5554a79bc3680a27285d56b080d647ade762d459","datavalue":{"value":{"entity-type":"item","numeric-id":2845034,"id":"Q2845034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43445a0dc98c612deed38ff2aa43edcf2fa6769a","datavalue":{"value":{"amount":"+0.90759504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260649$63C5EA54-8124-44E9-B6D8-F5A459B1E1CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5de8d645ea94cfff6fb2d58cea8be656984a1d2","datavalue":{"value":{"entity-type":"item","numeric-id":5929309,"id":"Q5929309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c660295501b211a8fc7759417dfbd6c13b928a3","datavalue":{"value":{"amount":"+0.9074651","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260649$53E55784-4136-4D10-A10F-AC76F65B21B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa0259bbca1ea003f96074b1512c567297538a4f","datavalue":{"value":{"entity-type":"item","numeric-id":1898204,"id":"Q1898204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2fa2dad527a7dc951343b817d48f4706938bb61","datavalue":{"value":{"amount":"+0.90533835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260649$EA0CF7D3-EFCA-4DAA-B5C0-9D35E13ADAB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0d5189b8481afa08e3bcc0d4cac4c05edbfa331","datavalue":{"value":{"entity-type":"item","numeric-id":2508774,"id":"Q2508774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6de1370a5d0e39e9549c81643608da8632882eec","datavalue":{"value":{"amount":"+0.90056336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260649$CE26F057-04CD-4319-968B-6BEC6076351C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79a39b20e32cfa3ebbfe0f9cf395712c510634a7","datavalue":{"value":{"entity-type":"item","numeric-id":1290161,"id":"Q1290161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8eb3a981c7be5a00180ce69d0152b5a6b28b705","datavalue":{"value":{"amount":"+0.8986134","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260649$8A628F77-9450-47E0-9BBF-68BA3EB0CD60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c53fd2c213839284e7520d81a8f23d86d0aba737","datavalue":{"value":{"entity-type":"item","numeric-id":2489280,"id":"Q2489280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9188661d968e5a9209dc55de520bbc19aa8b722a","datavalue":{"value":{"amount":"+0.89836","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1260649$F0C84EAC-F35D-4545-B1DE-52E5D27B1CAC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds and efficient algorithms for multiprocessor scheduling of directed acyclic graphs with communication delays","badges":[]}}}}}