{"entities":{"Q1104096":{"pageid":1114848,"ns":120,"title":"Item:Q1104096","lastrevid":42879277,"modified":"2025-07-15T16:06:05Z","type":"item","id":"Q1104096","labels":{"en":{"language":"en","value":"Communication-efficient parallel algorithms for distributed random-access machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4055053"}},"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":"Q1104096$DE626CE3-5C17-4FB5-B303-E09D9A9FCC02","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7f486ee050c6ffaa45b9f0ed9de0b49395482267","datavalue":{"value":{"text":"Communication-efficient parallel algorithms for distributed random-access machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104096$547F84F6-ACE5-48BA-9CF8-800820B69D43","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dbb94dbe1604b043c60ae4ac72005f73e8a684ab","datavalue":{"value":"0646.68067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104096$C9E7430E-38BE-4A27-B8C9-EBAEEB76E1ED","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cf8fd1e5b9f8e90058c898dadc92d44eba427b83","datavalue":{"value":"10.1007/BF01762110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104096$CB44B911-2A4B-4867-9B3B-B867686C27F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"859433638474683b6a5fc083b6901c9b15045cea","datavalue":{"value":{"entity-type":"item","numeric-id":255258,"id":"Q255258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$08DCE6D4-F477-4F08-8700-83F37F10A266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"20d0c58b8f39a06fee62b6809ffb311457ce74a2","datavalue":{"value":{"entity-type":"item","numeric-id":202181,"id":"Q202181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$B725BB67-3B2E-4BBD-BDD8-520C8F8675FD","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":"Q1104096$6D1A6F8C-7649-49DF-A802-B0DE5EA2927E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1104096$7DD026C6-83D5-468B-8C6F-D7689A415528","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e268a5369a447b0a28a8f7a6f4ba62b94ee0339b","datavalue":{"value":"This paper introduces a model for parallel computation, called the distributed random-access machine (DRAM), in which the communication requirements of parallel algorithms can be evaluated. A DRAM is an abstraction of a parallel computer in which memory accesses are implemented by routing messages through a communication network. A DRAM explicitly models the congestion of messages across cuts of the network.    We introduce the notion of a conservative algorithm as one whose communication requirements at each step can be bounded by the congestion of pointers of the input data structure across cuts of a DRAM. We give a simple lemma that shows how to ``shortcut'' pointers in a data structure so that remote processors can communicate without causing undue congestion. We give O(lg n)-step, linear-processor, linear-space, conservative algorithms for a variety of problems on n-node trees, such as computing treewalk numberings, finding the separator of a tree, and evaluating all subexpressions in an expression tree.    We give \\(O(lg^ 2 n)\\)-step, linear-processor, linear-space, conservative algorithms for problems on graphs of size n, including finding a minimum- cost spanning forest, computing biconnected components, and constructing an Eulerian cycle. Most of these algorithms use as a subroutine a generalization of the prefix computation to trees. We show that any such treefix computation can be performed in O(lg n) steps using a conservative variant of Miller and Reif's tree-contraction technique.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$710FF37B-C4B7-44E2-BF8D-100864795EDB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104096$AA2C9F35-B3F3-4127-A7CE-C09858D4994A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104096$EF7AB492-AAD5-429C-A7CC-6BB74C15A934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104096$B848BDD7-101A-47C0-8299-6A2278A6E4E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8a64ab4ceea0d0f0e5f8172ff079adebec9f42e8","datavalue":{"value":"4055053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104096$45628785-1B70-4849-B311-8B88B9B56396","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"685f3f135728ab4018b2ba008af8593628d69faf","datavalue":{"value":"fat-trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$1592068E-A8B1-481F-B375-6D3380CA8DB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e3255a2fecedb426b4887844d3bff8d35705d5b","datavalue":{"value":"load factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$DEE339EA-A930-409E-9380-B92E1296878B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f90139540a7d903d3d1c4be37d3cee7145f7063","datavalue":{"value":"PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$BB2E2969-C1AD-46CC-ADD0-796A59685946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bff8ed7364a28c45b6a2fa61c6488f016dff727","datavalue":{"value":"volume-universal networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$03D3A3CA-923F-4655-AF98-BE9D1588FE9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e40be0cac0cced1028c5884d4c6e242f9c794e07","datavalue":{"value":"model for parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$71E79D86-84AF-4C4B-98C4-13198378C48F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f61b03654f05f6156cb9781ddffe65f61487f51c","datavalue":{"value":"distributed random-access machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$DEC9E93E-15D9-4F3B-8B7F-CB2450C9D614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$4CA0013C-17C4-49DC-8F8E-4D45DA0819DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"575cf3f80bb33ac9e055dccf6164713293115580","datavalue":{"value":"conservative algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$A9B674FC-300F-4E6E-90FE-EB77C10D9B56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bec363d5ab768492b924e5946de1a220282d0cd","datavalue":{"value":"treefix computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$ACD88269-EB1E-4747-86E9-9EAA40FF0C7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6cbda12fee3a489d4843739145e842340d02ff5","datavalue":{"value":"tree-contraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104096$71B12776-823A-406C-8B2F-AA362AB25644","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":"Q1104096$E5301540-6C71-4707-9BF5-5919C45F3758","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4077de5ad21c6b78a25ec43c56119974484a370","datavalue":{"value":{"entity-type":"item","numeric-id":4401551,"id":"Q4401551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$14665CD7-B8F4-4FC2-8DBF-8A4914F25457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdb2be559bc16db998d32e6fa75898d44807cf88","datavalue":{"value":{"entity-type":"item","numeric-id":3934311,"id":"Q3934311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$432D990C-A95F-4DF7-9A84-FB98073AB170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77d6452e54e5e6983bfa6dba10e55824db2fd929","datavalue":{"value":{"entity-type":"item","numeric-id":5814290,"id":"Q5814290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$96247E22-0509-45B3-AD94-FDC06DCCEE2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508894c78bd2770d073dbe57a0316a7e71f6bc30","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$26128A05-9479-48C3-A10E-28B099D46B8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$BBDFC4B3-8552-4C79-9FD5-9D1BA5623B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd6de3de50fb0979d02f6151c82cfa63f5ddf149","datavalue":{"value":{"entity-type":"item","numeric-id":4190126,"id":"Q4190126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$775C511D-817A-43F8-9C2F-A7E45BAF5377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"615ef23fbcf67354e368f2ece5eb765e7b7589ff","datavalue":{"value":{"entity-type":"item","numeric-id":3753506,"id":"Q3753506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$54B959C8-9364-40E7-85D9-54463874A438","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$FB715C26-F071-42B7-B095-54DE1EC048A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65399e853feda19ca18081f77b141099f5c7138d","datavalue":{"value":{"entity-type":"item","numeric-id":5341755,"id":"Q5341755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$6EC9BA19-13D4-47FB-8E24-5E13FE7E5D4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9db4a207e2ab9eef002ed1bcd0688887d186bc","datavalue":{"value":{"entity-type":"item","numeric-id":3957960,"id":"Q3957960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$2BAE0A35-05F7-41B6-8854-7E2F6D99F5A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$BA3740F8-3C5B-4B1B-B7A7-DB5E5EA82E62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c16c0df08e375f0ed0eb72db2eb40af52a5b5c67","datavalue":{"value":{"entity-type":"item","numeric-id":3936664,"id":"Q3936664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104096$D26B06ED-E392-47DC-94B2-91E3ADE319B5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6727c42d0a087de4065f4f2c139587b52e7aa14","datavalue":{"value":{"entity-type":"item","numeric-id":4942231,"id":"Q4942231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1952790839579430e910c2663f7278207b707357","datavalue":{"value":{"amount":"+0.9159582","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":"Q1104096$AFD36017-6673-4997-8ED8-B21DF226E3D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7a5f7cb8e97ac11b35bd2b9180e538d87efd02b","datavalue":{"value":{"entity-type":"item","numeric-id":3765230,"id":"Q3765230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"474f1714520e96f20b8890602a6b3ebe4a3d8978","datavalue":{"value":{"amount":"+0.90520996","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":"Q1104096$BAEB6C54-D48C-4845-9FDD-D99B3981D0EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"895691fc6731936b4d0fe212b2f0a2c319e72504","datavalue":{"value":{"entity-type":"item","numeric-id":4260377,"id":"Q4260377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b08ffeb0dba19ed382e2b9f813e877823d398e3d","datavalue":{"value":{"amount":"+0.9018898","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":"Q1104096$2D26BC5B-6889-426A-B033-187635BEF58D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5df4c5594673fb17e1db0c4930ca0f8a365f757b","datavalue":{"value":{"entity-type":"item","numeric-id":2837508,"id":"Q2837508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec08c14b7d62009245878266cc6943842ab6c9d6","datavalue":{"value":{"amount":"+0.90013796","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":"Q1104096$B04B27D0-4BE4-45D7-AD04-109300D98318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41142a0d7fe8546b3e5dadc5f27bcf8c7f9ca1a9","datavalue":{"value":{"entity-type":"item","numeric-id":673529,"id":"Q673529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"257e518a2d27dbe87814d2c810e84486d2b58bd8","datavalue":{"value":{"amount":"+0.89658797","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":"Q1104096$09CAC345-2E5E-422A-BF87-5F536C0FE686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"345de88d92af9c2bba60edc0bfd59c50d50d8ac4","datavalue":{"value":{"entity-type":"item","numeric-id":380672,"id":"Q380672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39a27e948726a6910a461b5402c5c461098bfb27","datavalue":{"value":{"amount":"+0.895521","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":"Q1104096$DACFF2AC-6DFD-4A52-A11F-5D6D7CB0DEE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7415bb860e1e9a2fff433b0f49b1aec625b14ebe","datavalue":{"value":{"entity-type":"item","numeric-id":1575740,"id":"Q1575740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e16b235dd21892007ddd8852f24c8d435657aa37","datavalue":{"value":{"amount":"+0.8954981","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":"Q1104096$6EEE71D2-2185-49B9-BBAA-00C92C74543A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1104096","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1104096"}}}}}