{"entities":{"Q2272977":{"pageid":2283720,"ns":120,"title":"Item:Q2272977","lastrevid":78400055,"modified":"2026-05-06T11:30:11Z","type":"item","id":"Q2272977","labels":{"en":{"language":"en","value":"The first fully polynomial stabilizing algorithm for BFS tree construction"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7106199"}},"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":"Q2272977$4ABCB644-3EE0-40C1-99F5-CE63D0F85F9A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bb0e7d11cbfc635875c60b6ee77163f7b76907c5","datavalue":{"value":{"text":"The first fully polynomial stabilizing algorithm for BFS tree construction","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2272977$0FCBC80B-9188-4577-AB4F-C7738D132DC6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1e9e92cbdb10380d5765e05896f86ada25b8c53b","datavalue":{"value":"1439.68028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272977$97F4E33C-878D-4C5C-A04B-8477C1406F26","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4cbdd4c8607980ec1f7b7340803ff22dc5c28757","datavalue":{"value":{"entity-type":"item","numeric-id":264564,"id":"Q264564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$AE2581B1-45B5-4D6E-A271-B86BED061EE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f502a79c0a2b14eece32103c588af7b7cc65842b","datavalue":{"value":{"entity-type":"item","numeric-id":264568,"id":"Q264568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$16D4B2F9-11F3-40D5-AB13-55883A272FED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0eb538084cadf4afda91934b9c406f9813fd50f2","datavalue":{"value":{"entity-type":"item","numeric-id":388462,"id":"Q388462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$013F63B7-4540-4620-8E2A-54379DE013AA","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":"Q2272977$E58F1847-F5C1-4016-A2D0-0E22C5D672E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"860c75d427a5be90563ac8b1b9f2dee75426aaaa","datavalue":{"value":{"time":"+2019-09-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2272977$40EE12DB-94D2-461A-9E37-51DEBB6023B9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2169a2bc1e8ccdd38c1ed8795228e56fffe3ae09","datavalue":{"value":"The paper introduces a new class of distributed algorithms for constructing a spanning tree and characterized by a round complexity polynomial on the network diameter and a step complexity polynomial on the network size, namely fully polynomial algorithms. Moreover, an example of such algorithm is provided for constructing a BFS tree under a distributed daemon; the BFS tree construction is based on a snap-stabilizing algorithm. The new class of distributed algorithms is particularly suitable in the context of large scale networks, while the algorithms allow to have an execution with a high degree of parallelism, while the communication complexity is bounded.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2272977$A20663D7-DF2D-4475-BD47-F2AD3C406831","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272977$221FC94E-6F1E-444F-B6C4-F0E1ED9CDA27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272977$6F557C00-4107-4617-B398-73E2CB651611","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5e9733d0422d60970687c65d759067bbadd2adfa","datavalue":{"value":"7106199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272977$E1AF8ACC-A29A-4824-BC8A-DEDD1B412FC6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f82d9744537c8929843a9f698e900cd31ff81587","datavalue":{"value":"distributed systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2272977$1F576539-C37A-4559-9BA0-9A2502381463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2272977$368E84C1-8E1F-4CCF-BCFA-F64FFA07AB73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b01b02968c48df9f6d634df64bea355af4ca03","datavalue":{"value":"fault tolerance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2272977$63D95814-533D-4FBD-BB30-8E43253D28A2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2f9e16b52bc8c390b9fea0fb31de1975133dd070","datavalue":{"value":{"entity-type":"item","numeric-id":455938,"id":"Q455938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$0D6F7A34-1F57-478E-ACE1-17949ECBF0C7","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":"Q2272977$A6C9CD04-EC41-474D-B1DE-2D113110BC31","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8f01f2680a5b1c9feef8a36fb2924f9d69d9af19","datavalue":{"value":"https://doi.org/10.1016/j.ic.2019.01.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q2272977$46443038-A351-4E30-BDBD-9B2599E497E4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1953eeafcf34ed88701753f7c32d0efe3de1c2e2","datavalue":{"value":"W2913859261","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272977$2BA3893C-63A4-4499-85C7-494280AD7AE4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"235137c7b88cfbe9e3de0f801c8a5128819d04e3","datavalue":{"value":{"entity-type":"item","numeric-id":1882139,"id":"Q1882139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$AD98194E-7D32-4140-A029-3C11BE34365F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afe5701770dd978fee2e0976a672614cc2e373f8","datavalue":{"value":{"entity-type":"item","numeric-id":2900969,"id":"Q2900969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$2EE2255B-ED2B-4F17-9049-337E87658804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21a8eb34c519834b5b923e52b9f7343a721bfe4a","datavalue":{"value":{"entity-type":"item","numeric-id":4061976,"id":"Q4061976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$E23A1714-5498-4C9E-BC1A-088C99D74756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e230b3728d10ba582373bbcad97e70c9be621d32","datavalue":{"value":{"entity-type":"item","numeric-id":2782251,"id":"Q2782251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$82D33E95-E575-4624-A879-D80298584F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d368581606fa0b78f626e8ba11b24daf9524eab8","datavalue":{"value":{"entity-type":"item","numeric-id":4763060,"id":"Q4763060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$9242B56A-BA92-4CCC-92F2-99E706AAFD4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f5c5f157d0d28b3f6ba737b7a89e3fbcee56a4e","datavalue":{"value":{"entity-type":"item","numeric-id":3588323,"id":"Q3588323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$361215DE-F310-42CF-9993-84933FF29285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"074b161923be505c2eed14030e01c5e281e87181","datavalue":{"value":{"entity-type":"item","numeric-id":3357516,"id":"Q3357516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$83276C9B-E3FA-427B-AC87-1DCDF305DC78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e27c8c0994f77b2d7a8f31f03f9a62612aa4c50","datavalue":{"value":{"entity-type":"item","numeric-id":1182088,"id":"Q1182088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$D5DEC168-07CD-4639-8A28-5954ECA0F6C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c99eeac77643e896469d2c72f397216a7c690e7b","datavalue":{"value":{"entity-type":"item","numeric-id":1186586,"id":"Q1186586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$73B7E915-0AF2-4D2D-B8F6-8D2B35FCFE0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d76a95caa1ed1c1b11f0e51e932a099c1ad37691","datavalue":{"value":{"entity-type":"item","numeric-id":3523201,"id":"Q3523201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$53CA7A76-7139-44AA-8962-537651B16DF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4da6b2bdde924515f572ddd4df95727c17b1096","datavalue":{"value":{"entity-type":"item","numeric-id":5248536,"id":"Q5248536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$7A2EC5A2-B5FA-4C9B-91C0-6D7794B9138F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5895a66da601c0920a3476cd7346ab14b0157e4a","datavalue":{"value":{"entity-type":"item","numeric-id":1321819,"id":"Q1321819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$131E45A1-B32E-4F54-9CF3-4450A5F9680E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b069660552433698b154671e2ec8d00fc23a5337","datavalue":{"value":{"entity-type":"item","numeric-id":5307031,"id":"Q5307031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$15F6FDBA-1F0F-478D-9A07-5CFD3616CD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20e0956bb92f5818cc50366a7a3412df998f688a","datavalue":{"value":{"entity-type":"item","numeric-id":1870595,"id":"Q1870595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$B4E94016-0330-4733-8448-1359027BCE91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2000ceaca6f248f470859c6351d59283b2b7f49a","datavalue":{"value":{"entity-type":"item","numeric-id":719296,"id":"Q719296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$687CDBFD-5B8E-4327-9042-2A93BC00D256","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c42dd92f05746aa426ffb9b28981f758eae2ebb9","datavalue":{"value":{"entity-type":"item","numeric-id":645826,"id":"Q645826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$94747E4D-9AEE-4D74-A7B9-6325C3437AFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13f62f52d1640299bee3ad5efb18ba97452782fc","datavalue":{"value":{"entity-type":"item","numeric-id":5899119,"id":"Q5899119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$7076F7C9-6D0C-47E0-AC47-892FA2615C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efbbf0893dcab641f1ef1682f4f1382fb8cf28e0","datavalue":{"value":{"entity-type":"item","numeric-id":3408166,"id":"Q3408166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$5C3FE162-98A6-4702-B06A-7F515769911E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a526303c3ea949de7e9e885965b490733fdd688c","datavalue":{"value":{"entity-type":"item","numeric-id":528197,"id":"Q528197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$580A9881-24DE-4E68-8EC3-9D0D6C0D8A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0566d415668db9bb3d61a9252a66340084dfb65","datavalue":{"value":{"entity-type":"item","numeric-id":3313789,"id":"Q3313789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2272977$16B1185C-E146-40E9-A699-E71653F2325D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b4f8bb6ce7f7928442e6c104df1caeb6ece98cb0","datavalue":{"value":"Q128486239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272977$3E3646C5-15F4-42FB-AD92-8B2119EED94B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8746c6f5e548d75263fe716f0e79515f6d16b812","datavalue":{"value":"10.1016/J.IC.2019.01.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2272977$ACE64B91-2B70-4621-A101-745F6FF7AB27","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eff94a052eedd2ac8cfcfad8a590bfe2afd64b90","datavalue":{"value":{"entity-type":"item","numeric-id":2900969,"id":"Q2900969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3607deb2c0d43ef2671e0f57cac5dc0ace565878","datavalue":{"value":{"amount":"+0.9138007760047911","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":"Q2272977$04D726B8-5258-4256-A979-5F4B5224E21C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef456a299d804f6101d129d9c3704dccaaba648b","datavalue":{"value":{"entity-type":"item","numeric-id":3408166,"id":"Q3408166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e80ec8bb4706ac56f7c6df8849d9d0c1b107e25f","datavalue":{"value":{"amount":"+0.7880556583404541","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":"Q2272977$E53CE188-C31F-40AF-8CD0-B245F2FEF414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf036f86076c8a8fc32608ade2234824302ed389","datavalue":{"value":{"entity-type":"item","numeric-id":975469,"id":"Q975469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b52a840bd1aa606e1659b450a6791c1d7174544","datavalue":{"value":{"amount":"+0.7717912197113037","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":"Q2272977$1D984385-6CF8-4E4C-9DE5-66F067A179D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1387aa68abf8fe6ca6d2467e980a7d5127911977","datavalue":{"value":{"entity-type":"item","numeric-id":1903205,"id":"Q1903205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d79c02ad0a0e9b8135cf25c6839677d379fc9403","datavalue":{"value":{"amount":"+0.7445628643035889","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":"Q2272977$449913FB-49F5-4065-8CB1-B0B656A01D7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13be46b4ec6803ac28481bf57c8eff39b76939c0","datavalue":{"value":{"entity-type":"item","numeric-id":3523201,"id":"Q3523201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2eb36652552c53720fef235c2b6ab67d1bf1a49b","datavalue":{"value":{"amount":"+0.7435559034347534","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":"Q2272977$FACB3D81-35A8-4E60-902F-CF1C7F82480D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The first fully polynomial stabilizing algorithm for BFS tree construction","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_first_fully_polynomial_stabilizing_algorithm_for_BFS_tree_construction"}}}}}