{"entities":{"Q1095652":{"pageid":1106404,"ns":120,"title":"Item:Q1095652","lastrevid":49119427,"modified":"2026-01-06T15:13:49Z","type":"item","id":"Q1095652","labels":{"en":{"language":"en","value":"On mapping processes to processors in distributed systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4028885"}},"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":"Q1095652$9BFA541A-382F-451F-BE12-B25042C53BD6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b425163d57615454f16e7ad1084f2540278fc709","datavalue":{"value":{"text":"On mapping processes to processors in distributed systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1095652$05DB42D5-FA9C-4835-8014-869376E2B02C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a2c83fcf88e38fdc4be45fc2fb546c641caa4a0b","datavalue":{"value":"0632.68029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095652$2E4B4450-A582-4AE0-AF8D-79630593B212","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e47c81209595ef4dd5fc35e0a8cd1dc5463049cf","datavalue":{"value":"10.1007/BF01408172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095652$F4939681-8673-4CD4-B91F-BA95D1E2E571","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"87bb7a2c91ab52ebd2ceb6868f4a4ba13b1dbded","datavalue":{"value":{"entity-type":"item","numeric-id":1095650,"id":"Q1095650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095652$2C64E1E2-F89D-4E76-BEF1-4B9FA8D4E780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea63f93cadd23a193f33dffa78ce5f26a91d7b26","datavalue":{"value":{"entity-type":"item","numeric-id":1095651,"id":"Q1095651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095652$0A2949B5-1EF3-4281-A20D-FAFBFC94F095","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a32831c4e3f60d79ea2f79afb884ef69e4c8191c","datavalue":{"value":{"entity-type":"item","numeric-id":199286,"id":"Q199286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095652$C2108024-C933-4574-BC96-CD28214D9315","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1095652$EBB18757-D921-4A59-8808-8C284A66A4A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"740a7a041dc6add0ca0f2ebb966058990252ea04","datavalue":{"value":"This paper is concerned with the implementation of parallel programs on networks of processors. In particular, we study the use of the network augmenting approach as an implementation tool. According to this approach, the capabilities of a given network of processors can be increased by adding some auxiliary links among the processors. We prove that the minimum set of edges needed to augment a line-like network so that it can accommodate a parallel program is determined by an optimal path cover of the graph representation of the program. An optimal path cover a simple graph G is a set of vertex-disjoint paths that cover all the vertices of G and has the maximum possible number of edges. We present a linear time optimal path covering algorithm for a class of sparse graphs. This algorithm is of special interest since the optimal path covering problem is NP-complete for general graphs. Our results suggest that a ``cover and augment'' scheme can be used for optimal implementation of parallel programs in line-like networks.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095652$9F5E370E-E3A4-4D58-A710-4F912AAC2E38","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095652$2E00DF37-1607-47A7-A5D4-3AAB6B3AFDA9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6e8747021aa50b125324f1e3054e93a5cea6df7f","datavalue":{"value":"4028885","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095652$3167A3B3-A2D0-40C3-8718-2D14CF6C212B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb78669d1e1fb8a3a19b3ab6cfa4ee987cacb82f","datavalue":{"value":"graph covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095652$D3B53B6E-C16D-4EC8-8113-18B1C8064346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e15610ccc0b78af51851c0bb78645feb46f18845","datavalue":{"value":"mapping","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095652$2B8B7D94-3FB1-4C66-B54E-DC4EFE73E826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"380ed7b8ba032b4ac262998327787b94298e4c66","datavalue":{"value":"network computers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095652$094D5635-5BE0-43E0-B0B8-D35F7B0C0AEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"855af08d63de68a214880a14dc080a2a72230738","datavalue":{"value":"parallel programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095652$285BAA22-E37E-40C8-AE66-BD5818E95928","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b53e0ee175ec17c248eaaff1b5545db982549cb","datavalue":{"value":"networks of processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095652$DDC9BA7A-04E1-475A-BFFA-B9E76B56BB6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fc120f062a54b6baa1457657c4398c2680981d4","datavalue":{"value":"optimal path cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1095652$84716794-6BC7-40B8-A95A-886B6358EE65","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":"Q1095652$D8625127-0BFA-4D84-9D3E-730D176301F5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5baf418323818720c001a2c289ee4eeaeb96188","datavalue":{"value":{"entity-type":"item","numeric-id":3953148,"id":"Q3953148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095652$21D74DF0-966A-47F8-9554-088FA794DE4C","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":"Q1095652$63BC8513-0376-4C47-87F8-CD84D928423B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f984a76d33b502ce8030a3d08c9fecc669033c57","datavalue":{"value":{"entity-type":"item","numeric-id":4115167,"id":"Q4115167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095652$998F9BEF-DB9C-471A-8E9A-8FC69E9F5D16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a3679937e0b3f254ac30f41e2ac3b68561cd039","datavalue":{"value":{"entity-type":"item","numeric-id":4146248,"id":"Q4146248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095652$BD9A69A1-2F53-4AF8-94A6-31E097C685EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095652$267D84A5-DC30-40CB-A833-6D349E178682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b8ca49a5619f41a7a3d54dbe6b8ab44e8b6c16","datavalue":{"value":{"entity-type":"item","numeric-id":4052166,"id":"Q4052166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095652$E0049039-52C8-459E-AA58-0A37C1EDADCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2f3498f835a6d93e4fa4cac1b62340ea93abfc0","datavalue":{"value":{"entity-type":"item","numeric-id":4132557,"id":"Q4132557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1095652$27B51A73-2E4D-475F-BFA8-F9EFCBBCAA69","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"58446a9f10802b825b42118ae40512c258945bdd","datavalue":{"value":"https://doi.org/10.1007/bf01408172","type":"string"},"datatype":"url"},"type":"statement","id":"Q1095652$8843CB1A-A40F-4F05-9C62-26004AA16999","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dd061bccc00dcd4608880d299c59b729482a704b","datavalue":{"value":"W2052162800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1095652$14E550FF-5915-4813-8AEB-E0B9931107D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0fb9e51731bc80a02080f93b11566ed8fe2c648d","datavalue":{"value":{"entity-type":"item","numeric-id":4023577,"id":"Q4023577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fcefc48181497b2e4c2d55963cd005eddacc2fa","datavalue":{"value":{"amount":"+0.7790583372116089","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":"Q1095652$4C427AB6-84A5-4726-9F77-34BE161B35B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee7307f0c921383bc6ede24ff5874a7826c2662b","datavalue":{"value":{"entity-type":"item","numeric-id":4845367,"id":"Q4845367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb0963f8f2668fd82330d223ea878ff3cfa7051b","datavalue":{"value":{"amount":"+0.7790582180023193","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":"Q1095652$E4F1BD76-D6DE-4327-8424-EEC877779F88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6f798d15343af7498ae89693afff6ad119cbd30","datavalue":{"value":{"entity-type":"item","numeric-id":5289224,"id":"Q5289224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f58d7bf738df4831d539932af015dcdefe652cec","datavalue":{"value":{"amount":"+0.7738478779792786","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":"Q1095652$A0A06829-B0C1-4077-9B2A-41A2E31E1254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2513a86d9eda94563b43937d4c36c3d7c60fbcd","datavalue":{"value":{"entity-type":"item","numeric-id":4140892,"id":"Q4140892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faeb5f3ac63643b7b806358311f86e0dc3098a13","datavalue":{"value":{"amount":"+0.7468941807746887","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":"Q1095652$1C0C90B8-9F40-4727-A683-A25947CCB77E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"864a633fa72c7cf4e4163a0efe367ca3751ec4ed","datavalue":{"value":{"entity-type":"item","numeric-id":5286057,"id":"Q5286057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dccbeeb330cb39174ade53260805dc51786c2dde","datavalue":{"value":{"amount":"+0.745017409324646","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":"Q1095652$6A2CA889-A592-4D1A-8E31-56EE0C8BBE12","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1095652","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1095652"}}}}}