{"entities":{"Q1719030":{"pageid":1729771,"ns":120,"title":"Item:Q1719030","lastrevid":57494106,"modified":"2026-03-31T04:05:51Z","type":"item","id":"Q1719030","labels":{"en":{"language":"en","value":"Complexity analysis of new task allocation problem using network flow method on multicore clusters"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7017124"}},"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":"Q1719030$D079C5C4-9A39-4843-802D-B0269CBB929B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"809c167d1e352f7c2ea27e086d8706cb37a90634","datavalue":{"value":{"text":"Complexity analysis of new task allocation problem using network flow method on multicore clusters","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1719030$6DBC3B98-2A13-4121-ABB6-9416FB613DE7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f3484863c506f9744f7504af2b5c80db3b04a219","datavalue":{"value":"1407.90096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1719030$53A9F969-1076-4C20-A499-B982207D7339","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b32fb7392f9d3e12a017a2f0eb6b40fa1156a59d","datavalue":{"value":"10.1155/2014/723497","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1719030$D1CC6D57-99F0-4589-9B29-4BD2B0938BF7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1b5a27a1adaa1a643852d85acbbae164e79ba41","datavalue":{"value":{"entity-type":"item","numeric-id":1719029,"id":"Q1719029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$E980E534-1C94-4CEF-81D1-E1BA05C4B189","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc97bc0aff607b9c22ce37ffa18b6de85001d90","datavalue":{"value":{"entity-type":"item","numeric-id":86199,"id":"Q86199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$FF6E2372-20FA-47E7-9D97-FECFC744CE1F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"32a6dc046c0aa99508538df457dbadf7aa620337","datavalue":{"value":{"time":"+2019-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1719030$0329EA6C-DFD9-4ED3-9F4D-BAA34E7CCE95","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"13147ded1878b5b9b40873029c8a8872e3774214","datavalue":{"value":"Summary: The task allocation problem (TAP) generally aims to minimize total execution cost and internode communication cost in traditional parallel computing systems. New TAP (NTAP) considering additive intranode communication cost in emerging multicore cluster systems is investigated in this paper. We analyze the complexity of NTAP with network flow method and conclude that the intranode communication cost is a key to the complexity of NTAP, and prove that (1) the NTAP can be cast as a generalized linear network minimum cost flow problem and can be solved in \\(O(m^2 n^4)\\) time if the intranode communication cost equals the internode communication cost, and (2) the NTAP can be cast as a generalized convex cost network minimum cost flow problem and can be solved in polynomial time if the intranode communication cost is more than the internode communication cost. More in particular, the uniform cost NTAP can be cast as a convex cost flow problem and can be solved in \\(O(m^2 n^2 \\log(m + n))\\) time. Furthermore, solutions to the NTAP are also discussed. Our work extends currently known theoretical results and the theorems and conclusions presented in this paper can provide theoretical basis for task allocating strategies on multicore clusters.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1719030$04D9B5BF-2261-4654-9BA0-48509CE38B93","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e3ec0ebb66ad9a53653ec1e19a7608e786acef46","datavalue":{"value":"90B18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1719030$592762EC-6424-4703-ACA5-63678845EC19","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b4005a11c05b1d1ee949033ce515718e14ff6c4a","datavalue":{"value":"7017124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1719030$DA933863-B184-4752-B8B2-0C5E053D8535","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7fd7a1c6fa4fb41648b0082fe8afa406de3b9134","datavalue":{"value":"Q59071676","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1719030$0C2D7057-B018-4668-9B12-032D1C27357C","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":"Q1719030$26D6B9AE-B462-45DB-B2AE-BC3A29FB6469","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7da1d8994be819cf8277852961453480d32555ae","datavalue":{"value":"https://doi.org/10.1155/2014/723497","type":"string"},"datatype":"url"},"type":"statement","id":"Q1719030$B8A9B24F-03DD-46DC-9140-38F8B6A70A04","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cc281636535cad8357313a909ddab3918e648924","datavalue":{"value":"W2070026487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1719030$6F01DA7B-3A0B-40C5-A9E3-A2A5F7ABE940","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9dc2f7f952092927dacd0d7a73c8568f10e239b8","datavalue":{"value":{"entity-type":"item","numeric-id":2760245,"id":"Q2760245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$18519A38-1743-4599-AF21-50033597576E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5470f85efeddde87f3b4f7dca3c27592e806f96c","datavalue":{"value":{"entity-type":"item","numeric-id":3116006,"id":"Q3116006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$81DCDCF6-EE3F-4C9D-801D-3F1D287A00E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d111e4f40041ab68363f3b43adf01a2f987f656b","datavalue":{"value":{"entity-type":"item","numeric-id":4127388,"id":"Q4127388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$26EFFCC7-EDFA-42B2-BFAF-ED1421474917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf5ded74bf3fe0c055f8be77b20830406f4bdcf9","datavalue":{"value":{"entity-type":"item","numeric-id":3735072,"id":"Q3735072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$C959C1A6-9E86-487C-A7A4-BF7C1358B27A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9220ffe2b425a6dd97d9c347248bb664a70c5547","datavalue":{"value":{"entity-type":"item","numeric-id":5375353,"id":"Q5375353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$2E520229-2401-4100-BCEB-75678B47A6E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edf30fa071f67a1db9cf749e9d2f26083bc66722","datavalue":{"value":{"entity-type":"item","numeric-id":1408823,"id":"Q1408823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$1E0A0DC0-1989-4724-8A40-CB189773A835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$49584186-4BB1-4FC0-8E91-3864A969FBF0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44f01c436a4ee34b1140c0ba9a2edcfc38125dcf","datavalue":{"value":{"entity-type":"item","numeric-id":4571385,"id":"Q4571385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27d83b261d83ac261f2c2bd9474869ef54596af0","datavalue":{"value":{"amount":"+0.87155265","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1719030$6CDCE070-BEBC-49BE-A9E8-E0B3B02B3E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"457ab32611b0fd4e9821c96f1ec8d1e4296791a6","datavalue":{"value":{"entity-type":"item","numeric-id":2485119,"id":"Q2485119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db83ee2f0f0227ad2ae8b07d5756b38931d0dfc4","datavalue":{"value":{"amount":"+0.87012744","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1719030$455F1A42-7FD8-42F4-BEFB-B2358D555102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45d930bf102f5b69470ef7410468a4f8bd713364","datavalue":{"value":{"entity-type":"item","numeric-id":666258,"id":"Q666258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d1302b29c5bbf8ffa4040f709b6fb3962ecb0d7","datavalue":{"value":{"amount":"+0.8643384","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1719030$1534C9A1-5A6F-4B6A-8783-5DD8ADA73056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e2d47103320f5dab468b99879782dedea85bb96","datavalue":{"value":{"entity-type":"item","numeric-id":4304826,"id":"Q4304826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7202bb86c075162afdf8884fa37d88809b6cff3c","datavalue":{"value":{"amount":"+0.8601106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1719030$3E5DAA12-E7C9-4980-B5C5-549587A714F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ede35c37551b4c4fb796e439a07f5673ba45cd59","datavalue":{"value":{"entity-type":"item","numeric-id":4636440,"id":"Q4636440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09adfc041aaaaa173ff50a3f1f736a25d9731edb","datavalue":{"value":{"amount":"+0.85548025","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1719030$A1292F3B-F55E-4D49-B0CC-818C76EA144C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1b84f837c963f994cc1472484c957d972896c58","datavalue":{"value":{"entity-type":"item","numeric-id":3197596,"id":"Q3197596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e41b5d5d56c751d66faab28dc82e413f624f1543","datavalue":{"value":{"amount":"+0.85305744","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1719030$86EBCCAB-AACB-4E3D-BE81-8177DC31F7BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12afa7990fd05b1a1a306697bd8ccdd76758e9cf","datavalue":{"value":{"entity-type":"item","numeric-id":1910619,"id":"Q1910619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b48e8412b8452b98a450262093eb2f263769d83","datavalue":{"value":{"amount":"+0.8510947","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1719030$91730772-8143-45C4-8AA6-757A34726BA2","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"daf5f856a5d861312ad309ab567540337a5f61d6","datavalue":{"value":{"entity-type":"item","numeric-id":57050,"id":"Q57050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1719030$4B5D7363-5DA0-4051-95F4-0A715872717F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1719030","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1719030"}}}}}