{"entities":{"Q580985":{"pageid":582752,"ns":120,"title":"Item:Q580985","lastrevid":62924838,"modified":"2026-04-11T09:01:11Z","type":"item","id":"Q580985","labels":{"en":{"language":"en","value":"Algorithms for some graph problems on a distributed computational model"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4018398"}},"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":"Q580985$735D9E42-EB66-4D68-88C9-51510BF81E47","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"38863c750412ecd5da75765b0ed2fb0f60f56439","datavalue":{"value":{"text":"Algorithms for some graph problems on a distributed computational model","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q580985$7DCCAF1C-304F-48E1-B26A-3BDE355FA340","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d41fd31277c660145d98ce11e5bd1e33489bf8a6","datavalue":{"value":"0626.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580985$86BE9EF3-6F7D-48AD-9D17-7AE6C4EA4331","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"069a640f69b8703aab425b8d3bae13f43baf487b","datavalue":{"value":"10.1016/0020-0255(87)90039-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580985$A4E31B19-18C7-4309-9667-7025F6531822","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"80743cf87f8cb9c2bf7c3498f3888e95b934aa87","datavalue":{"value":{"entity-type":"item","numeric-id":580984,"id":"Q580984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$9ACD35E8-B2EA-4389-8D49-C2B9E09E48FB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$D116F118-211D-4993-929E-8C05689BA5AD","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":"Q580985$00EFC348-785D-430A-8657-7AA5A31CB9FA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fc3ea4eedbf31a77bc13736249b1f40a6fabc212","datavalue":{"value":"This paper presents distributed algorithms for some graph problems on a network model of computation. These graph problems include breadth-first and breadth-depth searches of graphs, recognition of directed acyclic graphs and strong connectedness, finding weights of all the shortest paths from a single source to all other nodes in a weighted directed acyclic graphs, and analyzing activity networks. The results of computations (i.e., the outputs) of all the algorithms but the algorithm for recognition of directed acyclic graphs are available in a distributed manner. For algorithms in such a computational model, two types of complexity measures are important. One is the time complexity, and the other is the message or communication complexity. Both of these complexities are obtained for each of the aforesaid distributed algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q580985$453AA932-F930-4615-9747-4D94DFA12801","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580985$A7719B3D-442C-4088-844A-03D9CE41ABB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580985$854A19F1-2E1B-4FA8-AB6B-2A155322A776","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2c393d346405924596b491fbc377e783739026bd","datavalue":{"value":"4018398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580985$A835A916-7A63-4E2B-9286-D4706FE8B73D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"387e204c6977d7b097ac93bf9a6ecf723e21df10","datavalue":{"value":"distributed algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q580985$F1165525-F597-47F4-BE10-23EF58278B2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e085984a5851a830262f6e97a827ed60b6108c0","datavalue":{"value":"graph problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q580985$B2D7C5AD-54E7-4455-A9C3-1264EA6B80DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4483789c3569a114b8e83e1e1ecad0e2423ccdbb","datavalue":{"value":"network model of computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q580985$3E8B83DF-2F92-4882-981E-3E0DE9E3D513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02d4cb9949d1e0e1b52bcd330c1219b250da26ef","datavalue":{"value":"complexity measures","type":"string"},"datatype":"string"},"type":"statement","id":"Q580985$5DEEE8F3-6B24-4FE2-B2C2-CDBFFE051EC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q580985$ABCC7D51-140A-41EB-A744-7FFAF519F30C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d59f9270ba2c0b3161162dab212fcc774a42eba","datavalue":{"value":"communication complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q580985$1D171A28-EBA4-46E9-8473-F8060E968A7F","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":"Q580985$FE128916-FF94-4EF9-9C97-34B9D7F0D2FB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"431679c7c9b4fa6359b9784e1eda062fc6cc526e","datavalue":{"value":"https://doi.org/10.1016/0020-0255(87)90039-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q580985$224CAE29-12A8-4300-ABF0-CC8370D89F53","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f3c221c059dc73c46afed29e0ca6a81c16eb1b9e","datavalue":{"value":"W2071155722","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580985$B16FB6BE-C6AB-4B17-BFBF-D7E82097282C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e2ab036340211124f0e0b42b404cab5811eb2","datavalue":{"value":{"entity-type":"item","numeric-id":3766876,"id":"Q3766876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$70BC7F43-C664-43F7-B3B1-E06CFE5CC2C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00d9ee0dcdf8442d977fb2b0e5d6a60f0f9d541b","datavalue":{"value":{"entity-type":"item","numeric-id":1062756,"id":"Q1062756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$46C07D63-9F57-4166-920F-1526BC9C7EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ace62efaa742c1d2e4fe601da1707f3045a7ce35","datavalue":{"value":{"entity-type":"item","numeric-id":3659168,"id":"Q3659168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$B7CFC3E2-11D6-4718-AC29-4F9D27F8C44D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd6ecca6b221a68c42607dd450ab7e9cb51b1138","datavalue":{"value":{"entity-type":"item","numeric-id":3945594,"id":"Q3945594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$C37E31F8-A677-4C93-926A-8FC66D461399","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f6f2fa62f920fb46fbd79ba851e5cbf1f877777","datavalue":{"value":{"entity-type":"item","numeric-id":3922163,"id":"Q3922163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$55B28E0A-EB0E-4906-A9A2-D20797714CF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af5166c86748afd1def80a8564f3c6d2883b0cf4","datavalue":{"value":{"entity-type":"item","numeric-id":1162156,"id":"Q1162156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$9CB08047-10EC-4996-91C9-4ECC9D39A8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c4f599c7e80cc4a63e588fa61d4f84934315f3e","datavalue":{"value":{"entity-type":"item","numeric-id":4154064,"id":"Q4154064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$690C34C4-C00C-46C9-AE73-B32F45D58839","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06b820d7730c4483ffdeaf5f1bb9567aad23b088","datavalue":{"value":{"entity-type":"item","numeric-id":3906428,"id":"Q3906428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580985$8DE32CDA-F687-4A4D-BD85-453991AD80BC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20b0588c6ec0b331d3318bf63bc82485aa2454fd","datavalue":{"value":{"entity-type":"item","numeric-id":3953185,"id":"Q3953185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87ec969061cefa5c16ab35905db420c3635a728a","datavalue":{"value":{"amount":"+0.7754866480827332","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":"Q580985$A06D2437-898B-4498-A91F-795EA2FC150E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"548a95361d5f8427213f271b02b8f100ee885df1","datavalue":{"value":{"entity-type":"item","numeric-id":1186357,"id":"Q1186357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c234ba494ac5da487f97ec2672db52acc1e2aa4f","datavalue":{"value":{"amount":"+0.7727283239364624","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":"Q580985$23F8FB9F-8512-4723-A53F-8D4F3B9E84FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"830ed7075d0fa4a45cad14fa7f49500436b98949","datavalue":{"value":{"entity-type":"item","numeric-id":1103409,"id":"Q1103409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8f811e7bbce492ee7384331d0d83c7102e13512","datavalue":{"value":{"amount":"+0.7677364349365234","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":"Q580985$5053C179-D42C-49E6-971F-2A003568C0C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2c6058877d93eec75800f4934441a3d51023f77","datavalue":{"value":{"entity-type":"item","numeric-id":3719849,"id":"Q3719849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d63c388a7d97e18afd7b6b6781fac53dc9a3ab30","datavalue":{"value":{"amount":"+0.7670084834098816","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":"Q580985$00F6C04F-52F6-4A88-8A4F-FC13B90B8429","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbd91ae1f9d514bbdc5b1cd49b75a7eaf18ddb62","datavalue":{"value":{"entity-type":"item","numeric-id":3148302,"id":"Q3148302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8793bdc7119433b071bb8870343412010579c1d","datavalue":{"value":{"amount":"+0.7637177109718323","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":"Q580985$FE5B84CE-2A54-4E8A-9543-9C933F2F0173","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Algorithms for some graph problems on a distributed computational model","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Algorithms_for_some_graph_problems_on_a_distributed_computational_model"}}}}}