{"entities":{"Q1111396":{"pageid":1122145,"ns":120,"title":"Item:Q1111396","lastrevid":66688725,"modified":"2026-04-12T11:59:39Z","type":"item","id":"Q1111396","labels":{"en":{"language":"en","value":"A parallel algorithm for recognizing unordered depth-first search"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076651"}},"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":"Q1111396$17BCE198-047D-49B0-A6CB-68F8826B7214","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"88a8a116a2691d4e0069cd9a32da3c5c2ea6164d","datavalue":{"value":{"text":"A parallel algorithm for recognizing unordered depth-first search","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111396$D79E0157-70E8-4334-A492-97B36CFD239C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8a44a78c88cdf46f9531000265e88d67b49f9525","datavalue":{"value":"0658.68083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111396$9C78631F-5038-4E4B-9E5D-AD7466431B97","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cbd5848fb6436a996f1af3e8e10bdea3e2b9cf87","datavalue":{"value":"10.1016/0020-0190(88)90172-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111396$5FAC3A33-6E4F-4E72-A668-9D788F8AB186","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"097e349ae1b3c10bbb9c0c5e12936116cc183b0f","datavalue":{"value":{"entity-type":"item","numeric-id":282653,"id":"Q282653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111396$E5DEAA82-FE61-4286-9C41-360BBB22402D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17acfb4cc6c6e051decf1aac30c199a8ac55c86d","datavalue":{"value":{"entity-type":"item","numeric-id":551182,"id":"Q551182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111396$E39F4CD9-E0AA-428E-8D89-90278553D820","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":"Q1111396$40D0B567-852A-4254-BF6D-018E65C75711","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":"Q1111396$2C7CA277-C9E4-484B-839F-9E74F6F57B2B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bfd8629a2e0b2defc4190d48549e13acf96f593f","datavalue":{"value":"We present a parallel algorithm for the concurrent-read, exclusive-write PRAM model that determines in \\(O(\\log^ 2 V)\\) time using M(V) processors whether a given directed spanning forest of a given graph corresponds to some unordered depth-first search, where \\(M(V)=O(V^{2.376})\\) is the number of processors needed to do transitive closure in \\(O(\\log^ 2 V)\\) time. If the answer is ``yes'', the depth-first numbering of the vertices is also output. The algorithm can be modified to avoid concurrent reading at the expense of more processors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111396$EA9507E5-0189-4256-A594-9AB83AD8E1F7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111396$1E23ADBE-A532-4FEE-BE87-6D85B07D2CF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111396$FC820C97-696A-4295-A385-7DF9F300EDCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111396$2D4DBC34-EF61-44C2-9036-166177203E29","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2fc0585a34f76f58c77d243e7627da1f4c371e4f","datavalue":{"value":"4076651","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111396$3C0A5C18-9E8A-4989-A516-BCAD2B25AE1C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111396$3E2E176F-8534-4B82-B581-49C44C6381F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7856d7105190ffa8dbea980e07ddca387824271d","datavalue":{"value":"concurrent-read, exclusive-write PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111396$237B42DF-0CD0-40C1-81B1-E5B71E3B451C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff7bf11626141f10491819543bc6e69eb57efdf3","datavalue":{"value":"depth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111396$B07B1DB5-7658-4B2D-A554-EC0EC5339561","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":"Q1111396$BCEED4C3-19C9-40DE-9A50-BD8880D4ADDD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5b29e8dddaf3838e2ed77b182b2738f0c5d0410","datavalue":{"value":{"entity-type":"item","numeric-id":1104756,"id":"Q1104756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111396$975408D3-EDB5-4AA9-9CDE-1A78F7075817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ead6d500c88a5f1fb0b5fb378d4b20ee226e811","datavalue":{"value":{"entity-type":"item","numeric-id":795509,"id":"Q795509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111396$F33CC609-FA52-4420-A7E1-4FEBF70D3257","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":"Q1111396$73EDC479-5889-4A88-83C5-8CEC662AF4D6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2e9dcc1eb579b93c85dbb6abb81744cf888cab1a","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90172-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111396$BCF1754C-1EFC-47F8-B120-FDBB638FF51F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3a061a5b97fc7493d4513121073ff87134a6f61a","datavalue":{"value":"W2093602721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111396$80CEE3B8-C085-4D4C-9991-35C71092601F","rank":"normal"}],"P1643":[{"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":"7d18d7425dac727116eaf1313693f918680f251f","datavalue":{"value":{"amount":"+0.8841827511787415","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":"Q1111396$CD0CD727-6B64-41D9-B773-7C063D5F71CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f0d65feb2a150d4b92dcaa4a25594df0d7228ed","datavalue":{"value":{"entity-type":"item","numeric-id":3474884,"id":"Q3474884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cc1ebc4d8a2e85025f3846e1828ccd9fd4175a6","datavalue":{"value":{"amount":"+0.8458980917930603","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":"Q1111396$1F17B19B-CB11-4A6F-9F43-ED37C006ABDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"700349cb55ae79214504609603b5fcd69a7a72a7","datavalue":{"value":{"entity-type":"item","numeric-id":3798262,"id":"Q3798262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"987dc85cc40f5712f62cca27b58e09799e89894a","datavalue":{"value":{"amount":"+0.8410937190055847","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":"Q1111396$C961DD61-054D-45A6-A449-17AAE74A9796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7df5b8b4adeb1d3682e50a8e612763d4791235b","datavalue":{"value":{"entity-type":"item","numeric-id":1104756,"id":"Q1104756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1171044edbd20e29b69dfa4abe3b40960340b768","datavalue":{"value":{"amount":"+0.8345856070518494","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":"Q1111396$8C0AFE35-1BD3-420B-860C-95DEE2AD20F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13e418a3a6cc453304e6913bf9528350171243a6","datavalue":{"value":{"entity-type":"item","numeric-id":685690,"id":"Q685690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6ac0d4769f893256af17d2577b3709088bc01db","datavalue":{"value":{"amount":"+0.8336713910102844","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":"Q1111396$8434FA14-2F47-4D98-BB47-5A8A3D4D518D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A parallel algorithm for recognizing unordered depth-first search","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_parallel_algorithm_for_recognizing_unordered_depth-first_search"}}}}}