{"entities":{"Q1111392":{"pageid":1122141,"ns":120,"title":"Item:Q1111392","lastrevid":66688698,"modified":"2026-04-12T11:59:39Z","type":"item","id":"Q1111392","labels":{"en":{"language":"en","value":"An improved parallel algorithm that computes the BFS numbering of a directed graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076649"}},"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":"Q1111392$FAE82FA2-DE67-4B14-AD20-7ABD9122B818","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eb83083c14cffa33fcbb73a5debf0aa96d5938b5","datavalue":{"value":{"text":"An improved parallel algorithm that computes the BFS numbering of a directed graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111392$C28C9DF8-B0D6-4902-B118-F3D9F76A49B2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"892cdf4d800a12f71f9f65676b4942453d4bdb40","datavalue":{"value":"0658.68081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111392$ABA94F5F-36F8-4655-A2DF-8EBDC84DF236","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7050804498174f8e10a2933f0cb22a7842d4b075","datavalue":{"value":"10.1016/0020-0190(88)90164-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111392$734C48B1-6985-42C5-977D-37B01C4052C5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d950b36b0469d77f04809e7908d5cfbcb471c53e","datavalue":{"value":{"entity-type":"item","numeric-id":1111391,"id":"Q1111391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111392$A6EFA2EC-B667-4EEE-BDA0-8D84980AA3B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29373d22cc965afe0313777aac5867e3ef096150","datavalue":{"value":{"entity-type":"item","numeric-id":1071802,"id":"Q1071802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111392$2108BAD4-C860-487B-A604-A7D309CCBDD7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111392$D23FD63A-5372-4FD6-A0EE-0F615892C206","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":"Q1111392$B2A72CB9-8825-4124-B192-C8D17AEA9F22","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"91f2ecb8f4107f4db06fdae94326869b0febe908","datavalue":{"value":"This paper presents a parallel algorithm that computes the breadth-first search (BFS) numbering of a directed graph in \\(O(\\log^ 2 n)\\) time using M(n) processors on the exclusive-read exclusive-write (EREW) parallel random access machine (PRAM) model, where M(n) denotes the number of processors needed to multiply two \\(n\\times n\\) integer matrices over the ring (\\({\\mathbb{Z}}\\), \\(+\\), \\(\\times)\\) in O(log n) time. The best known bound for M(n) is \\(O(n^{2.376})\\) [\\textit{D. Coppersmith} and \\textit{S. Winograd}, Matrix-multiplication via arithmetic progression, Proc. 19th Ann. ACM Symp. Theory Comput., 1-6 (1987)]. The algorithm presented in their paper uses fewer processors than the classical algorithm for BFS that employs matrix powering over the semiring (dioid) (\\({\\mathbb{N}}\\), min, \\(+)\\), using O(log n) time and \\(O(n^ 3)\\) processors on the concurrent-read concurrent-write (CRCW) model, or using \\(O(\\log^ 2 n)\\) time and \\(n^ 3/\\log n\\) processors on the EREW model.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111392$460FD168-D520-4D7E-8B3A-86FFF5204E70","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111392$888AB9EF-6C20-4C48-AF4B-CB88E9EDD546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111392$54D572C8-CEA6-41F4-B6A7-E5607B99D346","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"529ea5c961df906a8b114596b6cc3394c689506c","datavalue":{"value":"4076649","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111392$FFA60B5F-D4D2-4A14-A320-E55CDFDB5FCD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb9d9f33d35d0ddb911dd2af7b8f43af342f23cf","datavalue":{"value":"exclusive-read exclusive-write parallel random access machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111392$FBF54772-E474-4A26-BFAD-7644C086EF17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e466ddadae1b3430248f8e312b96feeca2d822f","datavalue":{"value":"fast matrix multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111392$E10251F0-65D3-4282-B5E2-7F7BF2A7610D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111392$569E3686-EC8D-489A-B02C-1F5D97ED7FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dfa71e439ec4028df02c3244a2a76dc52ffb0dae","datavalue":{"value":"breadth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111392$F4DA72A9-6811-499D-BC35-9AADB3F0D018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f90139540a7d903d3d1c4be37d3cee7145f7063","datavalue":{"value":"PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111392$69657519-70E3-407C-9162-1AD601F191FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f64d3f596da4c394916c178f7feaba3aa8f7d0d0","datavalue":{"value":"concurrent-read concurrent-write","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111392$0CCCAF30-EE8F-46B9-890B-7548CFBDD82F","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":"Q1111392$8416BA1F-76E0-46DB-A384-F157FAC66BA2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8ae47cdce44279c98784bf68ce6b7e492ed0b258","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90164-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111392$909FA6E7-5FDC-45D1-BF63-1F405A920C0F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6f50b34f4df941855ef8465f173cae62d29f9b69","datavalue":{"value":"W2088570605","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111392$4DCA1A42-1834-4B57-AECD-41C2AB2D25A4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111392$064D4376-5B8E-406A-964D-3A3B85C854C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aad5682a5deae9c22ad0d31344f3d9f95de62518","datavalue":{"value":{"entity-type":"item","numeric-id":799337,"id":"Q799337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111392$894F643A-D550-44D7-8FCF-99C775F450FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1746c0002a982167f6b872896509d0ce78aa9e","datavalue":{"value":{"entity-type":"item","numeric-id":2536323,"id":"Q2536323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111392$5CBD3EB1-270F-42A4-8BCA-507699E24F5C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46b167665b254a43a9a0ca3e8e54535e9de5a15e","datavalue":{"value":{"entity-type":"item","numeric-id":3318124,"id":"Q3318124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac0f069bb528c71e409669e54872f65d57121020","datavalue":{"value":{"amount":"+0.8425505757331848","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":"Q1111392$1BF1C89D-0CD2-4C0B-81FE-781F054C70C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3baa70217c982a685ed6506ff54a662aaffa50d","datavalue":{"value":{"entity-type":"item","numeric-id":3802639,"id":"Q3802639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c92cc92f7d8ee45104abc352dc9647c448776e49","datavalue":{"value":{"amount":"+0.7976323962211609","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":"Q1111392$085CE494-97DE-44F7-BC6D-EA880E7E2902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"575adca100d9e1c31e5cac775941a0fef25e2730","datavalue":{"value":{"entity-type":"item","numeric-id":290218,"id":"Q290218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bed8a27e79ed5ab5730b056e84138e2b4a0099e","datavalue":{"value":{"amount":"+0.7884330153465271","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":"Q1111392$A966FE04-A1CB-464F-B4C7-198C75EB235F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ebd20a34f0ec5baf0d7dab9cec77e3e4019655b","datavalue":{"value":{"entity-type":"item","numeric-id":3802640,"id":"Q3802640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1889824df56e0055d7b6ee7ecbf406b28b7eab9c","datavalue":{"value":{"amount":"+0.7837157249450684","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":"Q1111392$C59CAEF1-BA85-4B49-8C6F-149B17D2E351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17a9cc4f2053bf06704ae53d48c6a7e2ca592309","datavalue":{"value":{"entity-type":"item","numeric-id":1209343,"id":"Q1209343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82b0ede8d75990eb5bb5dee62b2fa7a3c0aee40a","datavalue":{"value":{"amount":"+0.7793906331062317","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":"Q1111392$E6B147B0-331B-4777-A2B3-79B626428A4C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An improved parallel algorithm that computes the BFS numbering of a directed graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_improved_parallel_algorithm_that_computes_the_BFS_numbering_of_a_directed_graph"}}}}}