{"entities":{"Q1116343":{"pageid":1127092,"ns":120,"title":"Item:Q1116343","lastrevid":69678843,"modified":"2026-04-13T08:39:46Z","type":"item","id":"Q1116343","labels":{"en":{"language":"en","value":"Parallel depth first search. I: Implementation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4088942"}},"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":"Q1116343$4BC3BCB0-3A25-4DAC-8791-D6F63B0AFEA1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"62859a5af5aac2593f5ec1d777ebad88bc3b994d","datavalue":{"value":{"text":"Parallel depth first search. I: Implementation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116343$327EA314-9522-483E-AE0F-AE32141A4760","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"42f06128e53245dbd8604974591c461a763ecdcd","datavalue":{"value":"0665.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116343$AF922C24-953F-4645-822A-7580CCB9A40B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d1097f52d989c56ca94963c6b5bee4eac1215c5d","datavalue":{"value":"10.1007/BF01389000","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116343$A4B47EE4-5BAF-418A-B038-8AEA90DAE16B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86da95605b5765643367eb332c6180e629d734ab","datavalue":{"value":{"entity-type":"item","numeric-id":1116342,"id":"Q1116342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$3487C7F8-6B57-48DA-9EE6-99FC9BE466C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"653dbd7e14846e2e23dca7e70a3ad295299a6120","datavalue":{"value":{"entity-type":"item","numeric-id":551858,"id":"Q551858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$BC5D01F5-D102-4FA5-AC5E-758831BD354C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a32831c4e3f60d79ea2f79afb884ef69e4c8191c","datavalue":{"value":{"entity-type":"item","numeric-id":199286,"id":"Q199286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$6459099B-0CC2-4998-9AC7-40241466301A","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":"Q1116343$0C186F2E-DD4B-47C0-9D6F-8E45E5FA5F92","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"776b3c2dd7c610ce55b29e576f93133c5b5fea35","datavalue":{"value":"The depth-first search (DFS) is one of the most common techniques used in artificial intelligence or for solving various combinatorial problems and constraint satisfaction problems. Since many of the problems solved by DFS are highly computation intensive, there is a great interest in developing parallel versions of this algorithm.    The paper presents performance results of a parallel formulation of DFS run on various parallel computers (Sequent Balance 21000, Intel Hypercube and BBN Butterfly). These results clearly show that while retaining the storage efficiency, the DFS can be speeded up by several orders of magnitude. Moreover, if parallel DFS expands fewer nodes than DFS, a speedup of greater than N using N processors can be observed (speedup anomaly). The authors' experiments also show that hypercube and shared- memory architectures are significantly better than the ring architecture. The main conclusion of the research is that the effectiveness of the parallel formulation is strongly influenced by the work distribution scheme and architectural features of the parallel computer system.    As general remarks, the paper is self-contained, clear and of high quality. It is intended for specialists or students in final years in the field of artificial intelligence and parallel computers. [For part II see ibid. 16, No.6, 501-519 (1987; Zbl 0665.68049)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116343$182CEF0E-AB6C-4080-8469-EBCE0F1CDA11","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116343$81C2A757-E742-4479-989A-D25CF2B8C8B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"517ace4a4f9c45a5475b4a8927a567447dbdb293","datavalue":{"value":"68N99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116343$C019AA9E-373B-43F3-AC50-10861817808F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116343$1E8D9117-F751-43A1-B9F0-CFC9AF2406E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116343$CA8993F7-D1A5-4863-9EF9-B3909FC548F6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7eadb737eb37d9401094fdf3cbb78d24c056ad3e","datavalue":{"value":"4088942","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116343$5F0513D2-DCD8-43DA-95E1-87FA85A6BC39","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d3468555107fb2d08bf888d5244ffb101861fe2","datavalue":{"value":"parallel formulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116343$05497C3A-2A9C-48F3-897D-F70F7B6C11CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1c039bf0f3abe133aa1aa20d12481d898b74b99","datavalue":{"value":"state-space trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116343$8C5078F0-203D-4E96-A68C-19FDD28CC66C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff7bf11626141f10491819543bc6e69eb57efdf3","datavalue":{"value":"depth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116343$22B85E27-40A1-4D23-AB58-6D956E7BD8C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f056909eb37a69445bcbd768d8cc9a68320f3a4","datavalue":{"value":"performance results","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116343$06B5316E-8E96-4322-9086-8D0DEC726997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ec0505de8e13efe5e4cfceeafe66aeba9d35e29","datavalue":{"value":"parallel computers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116343$5625B01C-DF03-4AFA-B1D5-91768BD858F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31615d081e26ef80f2db81d0dda03dc29424f3f4","datavalue":{"value":"work distribution scheme","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116343$EB9F7E6F-B103-4E8E-9CAD-95CFD329ADA8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7fe7620e945054cf6aa8da466a7cb93509e71b4a","datavalue":{"value":{"entity-type":"item","numeric-id":1612676,"id":"Q1612676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$AC908294-AABC-4AF3-A4CD-9BEB9961F7E4","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":"Q1116343$C69CE222-FFD2-40CF-A305-F228646A155A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2ac6dc8bd7c9364a72b746abc774933838636e0","datavalue":{"value":{"entity-type":"item","numeric-id":1116344,"id":"Q1116344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$4E6FA9D3-423A-4C8E-B43D-8E63B27D1486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c52b21e2b050930655d553363cf317d38372f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3885184,"id":"Q3885184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$755B89F6-E22F-4F16-8A6B-A48E53AA4749","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1f0b5c5d1ef7da893967c1b74defc4984f71dee","datavalue":{"value":{"entity-type":"item","numeric-id":1062761,"id":"Q1062761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$7C0DE9AF-A52B-4650-A3E1-04347DF28BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ecb2f8db87b095bb3a0c58a549a6a7976f43870","datavalue":{"value":{"entity-type":"item","numeric-id":3309033,"id":"Q3309033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$9EB0A922-F656-468C-87AF-465533A021B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3c8227370b23a709289df885ca01c57567c658f","datavalue":{"value":{"entity-type":"item","numeric-id":3856120,"id":"Q3856120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$A958B899-EAB7-493E-98F6-D900375F9155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71668d6828349380b789e3532cb8b33e13077b91","datavalue":{"value":{"entity-type":"item","numeric-id":1837544,"id":"Q1837544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$96D2D8F7-2137-4996-9BAD-03BB725D6587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a9872f5615ce81662b5bdea00792d9325766452","datavalue":{"value":{"entity-type":"item","numeric-id":792768,"id":"Q792768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$104D0C7D-EEE9-45C5-8D4E-38768A63618B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf81e6d9c234339876089445bc7b93bc07a95490","datavalue":{"value":{"entity-type":"item","numeric-id":3713596,"id":"Q3713596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$E978E7E4-DAFE-40F7-B5E5-28659D31352B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0bb7c4cb2d8f4b5c5a6ce8363ba3de0e5afba49","datavalue":{"value":{"entity-type":"item","numeric-id":3817622,"id":"Q3817622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116343$99D06925-46C6-408A-A006-1D30C8D812D6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ee744eab885bf9c08e8da6d74dca6a7c11b920dc","datavalue":{"value":"https://doi.org/10.1007/bf01389000","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116343$30590F65-1AB1-47DC-AE26-F68A00AF0551","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7efad4f3bb4364730be60488885141910f76d51e","datavalue":{"value":"W2031960564","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116343$CBEC40D2-FEC7-4D85-9458-55A3A9B9B38D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"746684b63872768931eb524bd46e309f4d4b56c3","datavalue":{"value":{"entity-type":"item","numeric-id":1116344,"id":"Q1116344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef220eaef1a1eeea1c6a5f0656058e4f8b360166","datavalue":{"value":{"amount":"+0.8546402","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":"Q1116343$2845D4FB-CCE3-4E56-AD1F-6155A0EB3F50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bcf8afd6d4179bdaad67addee800f83dd7a8dde","datavalue":{"value":{"entity-type":"item","numeric-id":795509,"id":"Q795509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf6e1ac7ee64636564866625c1910260630ccc18","datavalue":{"value":{"amount":"+0.8482909","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":"Q1116343$72393D54-23E8-4B93-B07B-FEF33B9CDD45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3acfd31ff20896bd1d5a92c6b5ffd4dcfcf243c2","datavalue":{"value":{"entity-type":"item","numeric-id":4537127,"id":"Q4537127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10422413a73d873f9407fbb89a4e9f19a8a30625","datavalue":{"value":{"amount":"+0.822798","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":"Q1116343$4AB1B832-A832-4F39-BD2D-DEF3DAEF37BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b2bbc3284be4383c365961bef456e4fbaa06abb","datavalue":{"value":{"entity-type":"item","numeric-id":5418744,"id":"Q5418744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e90c4f656b96ca4d3a76a38c095db855d1e29adf","datavalue":{"value":{"amount":"+0.82173324","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":"Q1116343$088039EC-9671-4B90-841D-8A2DD7587DE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b9f122e0a37e05ae59aa63bf3b770538dc35e37","datavalue":{"value":{"entity-type":"item","numeric-id":3817622,"id":"Q3817622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"804554a83943b828c25c26009e066e719b424ef1","datavalue":{"value":{"amount":"+0.8183401","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":"Q1116343$3DD8B6C8-46B9-493A-B877-A388C58D6AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92ff75a81eaf1e77a895e70cdd80720e8e9d60ad","datavalue":{"value":{"entity-type":"item","numeric-id":1075058,"id":"Q1075058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e291036555037429e368c64477037de3e0d5b759","datavalue":{"value":{"amount":"+0.81440216","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":"Q1116343$68AA33B7-9469-4382-8D46-72C10D08FAB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66a3bbef8c737176b04e25d6fd8eef29404cbce2","datavalue":{"value":{"entity-type":"item","numeric-id":3753502,"id":"Q3753502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a3d1f016ada433386bcf280522ceee2adf449e0","datavalue":{"value":{"amount":"+0.8108075","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":"Q1116343$46363DC3-9945-4FBA-885B-CF9985EBA329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94be0cd6c84342d60b50fc22a00c27d8e58f632e","datavalue":{"value":{"entity-type":"item","numeric-id":5919087,"id":"Q5919087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24396804a06c1f60d597106aaa7a23f56c93c23f","datavalue":{"value":{"amount":"+0.8099349","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":"Q1116343$62B83AAC-94FA-46F2-BBC9-D9603E7B5E48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4326f7b5449ff9a726f981e4f2cb9c87296baadd","datavalue":{"value":{"entity-type":"item","numeric-id":4790466,"id":"Q4790466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6e2d70653b820d40279c4e8b0817d6a16b3fbbe","datavalue":{"value":{"amount":"+0.80789065","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":"Q1116343$32D8314B-8C79-4E55-86B2-85B6251FEDD7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel depth first search. I: Implementation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parallel_depth_first_search._I:_Implementation"}}}}}