{"entities":{"Q1062459":{"pageid":1073211,"ns":120,"title":"Item:Q1062459","lastrevid":66061500,"modified":"2026-04-12T07:16:35Z","type":"item","id":"Q1062459","labels":{"en":{"language":"en","value":"An optimal parallel processor bound in strong orientation of an undirected graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3913698"}},"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":"Q1062459$5F4153E6-835D-420D-A7E5-B1A07007320A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2574ba59ac9dacc0c01ba724356ca2f0015277e9","datavalue":{"value":{"text":"An optimal parallel processor bound in strong orientation of an undirected graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062459$31427858-6E4F-4C8C-BF8A-E90389156E22","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c125cb2ad8a6fe8e8f3266902460f6e3064fe4bc","datavalue":{"value":"0572.68054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062459$45B5E6C7-E6DB-4257-AC67-AB1378735CD0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"78dd28ae820a50007722ebe327fb925a59d6f94f","datavalue":{"value":"10.1016/0020-0190(85)90082-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062459$803CC44B-0D56-4052-8F08-B17B9EB0AF65","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4a117cfc97ede053829a4109bbebd5c69e5067c","datavalue":{"value":{"entity-type":"item","numeric-id":1062458,"id":"Q1062458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062459$78F02DE9-C4C4-40C1-BCE3-2F94C0271405","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":"Q1062459$F80A4470-D1FE-4819-8B57-33DD2963565C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1062459$A28868DF-F434-4503-80BE-0B11939971E9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ff0380bd3118bffccb6b0f23eef8ad901f22413","datavalue":{"value":"Recently, \\textit{M. J. Atallah} [ibid. 18, 37-39 (1984; Zbl 0532.68065)] presented an algorithm for assigning directions to the edges of a connected, bridgeless undirected graph so that the resulting directed graph is strong in the sense that there is a directed path from u to v for every two vertices u, v in it. Atallah indicated that a direct implementation of that algorithm takes \\(O(\\log^ 2n)\\) time with \\(O(n^ 4)\\) processors on the PRAM - a SIMD shared memory model allowing read but not write conflicts - where n is the size of the vertex set. He then proceeded to give an implementation which takes \\(O(\\log^ 2n)\\) time with \\(O(n^ 3)\\) processors. Our aim is to present an implementation which takes \\(O(\\log^ 2n)\\) time with \\(n\\lceil n/\\log^ 2n\\rceil\\) processors on the PRAM. This result reduces the number of processors used by a factor of n \\(\\log^ 2n\\) and is optimal for dense graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062459$52E20220-2D58-464D-829E-456AFB53BEFC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062459$D7E27A82-8C60-44CE-97CF-49F094EAA43A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062459$CBADB83A-82FD-4E98-A7B5-46457F97EA67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062459$D697651D-080A-437D-BA08-AB49A4F38EC1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a20ebb77c90d1c875eaef5e9cd87c79e889adda7","datavalue":{"value":"3913698","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062459$66B70BF5-C588-45F5-BB05-464703BE69A5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6604b135ad29578febd94d7f624bfe4c31d9c48","datavalue":{"value":"parallel graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062459$31C1C636-B909-41BC-BBF1-914152CFD4F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062459$D6DF516A-7E1D-462D-909F-65D37BB25169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062459$307F07C5-D8AD-4314-A314-4B195D3D51D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e84ee48586814a40f00ca811bc22a55bf16a558","datavalue":{"value":"undirected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062459$CEAD1B99-3889-4905-AE61-974A1CA00460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f90139540a7d903d3d1c4be37d3cee7145f7063","datavalue":{"value":"PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062459$A50619FD-2056-4CB8-AE36-1BC064605D94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d95f9885ed870903a9bef01d1946c19d61eafb6","datavalue":{"value":"SIMD shared memory model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062459$9F8C9779-BD31-443F-BDC4-582484DC5B14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d945464ea52d0483fab7a868292502c1a49c4dc","datavalue":{"value":"dense graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062459$D26A0A36-41D5-40F7-8423-81E5800FEDEC","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":"Q1062459$0FBBF6D1-8F03-4DE3-9653-41CE871729C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b304d7cdd7648b8babfe66c051510fea07e0722","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90082-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1062459$1A4E3FCE-3EEA-4904-8E23-045D956DB34B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e841d71532698db62cd7e34ab3c36fda8d48955f","datavalue":{"value":"W1991539193","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062459$6E987772-AB86-42A6-ABA2-0A48ED45B9B3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52f159acbc27707dcb36281d2b1f020e8eb1a93c","datavalue":{"value":{"entity-type":"item","numeric-id":789182,"id":"Q789182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062459$0D9A8572-9698-4148-A1F3-98219F79926D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5df19fdc79e639fa6b04eaaae6c2bf3cdb41c8b","datavalue":{"value":{"entity-type":"item","numeric-id":3335006,"id":"Q3335006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062459$AA3FA1FA-BEE9-4699-A2F6-A14BD2D0537F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23312e274b24b80b5a074972f6d85c96afb9b6fc","datavalue":{"value":{"entity-type":"item","numeric-id":3721831,"id":"Q3721831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062459$A1C8528C-2C96-4CD8-A85F-1DBE937424E6","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":"Q1062459$9F77FD48-DC30-460F-8843-F73B0037ECDB","rank":"normal"}],"P1643":[{"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":"aae6cf7ef9ceaad175f22aebafd2a7d9e808475d","datavalue":{"value":{"amount":"+0.9058552","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$0F98CA20-CA00-40A4-AB24-E6C7DF6DF83F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f624e442c81b4a50d9e36abfca679e6c98e96f13","datavalue":{"value":{"entity-type":"item","numeric-id":3815886,"id":"Q3815886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c55303e852c26803e849aeea59dbc2a5ecc68522","datavalue":{"value":{"amount":"+0.883662","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$2966E00C-1D5C-4C5D-B45E-ADC6787F3879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a42dda642f561b70535d81c2f73c938e42cea84","datavalue":{"value":{"entity-type":"item","numeric-id":5939271,"id":"Q5939271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81f114b59c3c946272ab5aeda221b32d1bb7ff32","datavalue":{"value":{"amount":"+0.8802371","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$42D86088-A48D-4DF0-AEE7-ECD5322E2F66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"918e95226794ad94abac30a47942ff80d43dc92e","datavalue":{"value":{"entity-type":"item","numeric-id":789182,"id":"Q789182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ad78e5835de7844207054e871b894703d9fd2eb","datavalue":{"value":{"amount":"+0.8785997","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$50922D31-9C57-4711-9971-88C0CD6D4741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01d01bc8602506d6d385d3385f21e11054941016","datavalue":{"value":{"entity-type":"item","numeric-id":3795245,"id":"Q3795245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"706874f5dbad62f7c83202252d8fa49e2e4077f6","datavalue":{"value":{"amount":"+0.87522805","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$EAA90612-B36D-45FF-9BE9-90C63FC9B0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5470b3c02779dcd80e9c9f1296b859acee2bcb2","datavalue":{"value":{"entity-type":"item","numeric-id":582094,"id":"Q582094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"706874f5dbad62f7c83202252d8fa49e2e4077f6","datavalue":{"value":{"amount":"+0.87522805","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$4CA082E5-B41B-4090-9D93-88A7669F5F60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20598589339d3a72fc5a17ddffed959b1eb8f06a","datavalue":{"value":{"entity-type":"item","numeric-id":3335006,"id":"Q3335006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c43a67d9abc4e647b00103ec1be41f2e47e7183b","datavalue":{"value":{"amount":"+0.8730924","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$D12CB4E5-C5EE-4593-A108-DECEC20949A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4988c8c3fcc8686751dd1179a13dcea06b4f1af6","datavalue":{"value":{"entity-type":"item","numeric-id":4864433,"id":"Q4864433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"065e58e18df943c980fd806da29bb9a9e2720440","datavalue":{"value":{"amount":"+0.87258804","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$47788345-B4B8-4426-9666-006BE4E43F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"714debca38c8f2afb69085b92169169357403e59","datavalue":{"value":{"entity-type":"item","numeric-id":3828023,"id":"Q3828023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9319d992ba8f8973b51c0a00f294f83f369840bd","datavalue":{"value":{"amount":"+0.87063795","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$45B13881-ED4A-4F46-8370-31A91CBC16BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"890f16baf1031fc17d8d502413d0639ac6c290a8","datavalue":{"value":{"entity-type":"item","numeric-id":3361906,"id":"Q3361906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4d2d0cc0f640de410fbba4ec0c7199b8c866a9d","datavalue":{"value":{"amount":"+0.870052","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1062459$3D396B01-655F-48C1-8D84-2F682DAE6D68","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimal parallel processor bound in strong orientation of an undirected graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_optimal_parallel_processor_bound_in_strong_orientation_of_an_undirected_graph"}}}}}