{"entities":{"Q1104756":{"pageid":1115505,"ns":120,"title":"Item:Q1104756","lastrevid":66725967,"modified":"2026-04-12T12:26:13Z","type":"item","id":"Q1104756","labels":{"en":{"language":"en","value":"A random NC algorithm for depth first search"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4057019"}},"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":"Q1104756$591FD34C-936B-4F71-A882-3E5A839DFAFC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"54285d24bcec4f7e0ce67fadf8ba93e7d9f15438","datavalue":{"value":{"text":"A random NC algorithm for depth first search","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104756$B55BC5E6-E0BF-4111-BE28-B8A650DB9B55","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a5b466bd8df87acb1c37c868b3dc79cc34361d1","datavalue":{"value":"0647.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$53EEC3D2-BA40-4F20-85D8-D30AB20427E2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a1f999feb4385263dbb0afc0556065f0168c0846","datavalue":{"value":"10.1007/BF02122548","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$CA4656E4-F2AA-4589-9BD7-B16D4C26A448","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aedf720352fcca932fab3523c4bbcafd7c4c7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1104176,"id":"Q1104176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$A6C9CA83-ACF4-418F-B0B1-CE5F969D4323","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$164D64C5-9841-48FC-8E89-CDD697831C94","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":"Q1104756$B9931F66-764A-41C0-9BB9-28F5FC93F72E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"95dad0fc65c2128d1aad8c1f65f0230582d8dc80","datavalue":{"value":"We present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithms is an RNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on a P-RAM. The run time of the algorithm is \\(O(T_{MM}(n)\\log^ 3 n)\\), and the number of processors used is \\(P_{MM}(n)\\) where \\(T_{MM}n)\\) and \\(P_{MM}(n)\\) are the time and number of processors needed to find a minimum weight perfect matching on an n vertex graph with maximum edge weight n.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104756$955A8C4E-56F4-4F8E-9437-F3A60F899FBE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$FB53368C-7B7C-4C79-ADE2-AB848D7B8AB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$5E44DCB6-BE58-4B6D-9F19-47065C9C04C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$B8CDCF31-AD4E-4397-AC47-901BA3E7FD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$96E2D1E6-E475-4DF7-AB53-A1BD00A38AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$8DCE2CDD-0A22-41CF-B973-6157C473FAFE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"999c0d516e38e10f7364685711595666ff054df2","datavalue":{"value":"4057019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$D8F4B338-7C42-432C-A324-8731B004E876","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3755a65c0459f7da1edf0c6ae50239987cd05a15","datavalue":{"value":"random NC algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104756$8CBF66FF-A7C0-4F88-9019-E102C009C840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"420ce17edce0510d0a89ced743b22f63125ab6ae","datavalue":{"value":"depth first search tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104756$9494BCE8-C76B-41DD-9456-53443076CA77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e84ee48586814a40f00ca811bc22a55bf16a558","datavalue":{"value":"undirected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104756$3F64970D-8B73-439D-A078-8BD41638E1AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"947f2f258df8e8ba91aa6c21666ab91e3b19cf65","datavalue":{"value":"P-RAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104756$6AC09BF4-824E-42FE-BD1F-D2D5E5068FCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e374d8525238efe155d23fddd171f6c6d9279fc7","datavalue":{"value":"minimum weight perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104756$824AB20A-184A-4917-BC3E-4938A1D4CF59","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"44908d56b87c7e395aa54e56f55b69e2b08c7aba","datavalue":{"value":"Q56114900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$149CF905-F9FC-4079-94D6-41828FC37407","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":"Q1104756$541FA394-1419-4E2D-94EE-D7367002A98B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ef1f1ad2c5f8506b736c58fae2d3e4ca486568f","datavalue":{"value":{"entity-type":"item","numeric-id":1100916,"id":"Q1100916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$71023A04-6454-4E6E-92C0-178C88479DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$4B5A7B5C-A278-416A-AE0D-0F00EEDE9A6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c993e07f76ed3097850c2bd4b835040acdee8efc","datavalue":{"value":{"entity-type":"item","numeric-id":4195963,"id":"Q4195963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$E273C0B1-4EDA-438E-9600-924641CBD793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8938235e226586e0d42dc09ecbb90514ca80ee6","datavalue":{"value":{"entity-type":"item","numeric-id":4094634,"id":"Q4094634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$16F0F89A-4E8D-4615-8162-4B2AC4D242E9","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":"Q1104756$B4C73FC0-F37E-4B98-9552-BC66EB09660B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9b712e361bbfbc97c265dcc3e2463de06c2cf58","datavalue":{"value":{"entity-type":"item","numeric-id":1103639,"id":"Q1103639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$F5647113-90F3-49BA-AB70-FE36736BDE96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee77505f29649c24a657424f3dfd6852fee0eca1","datavalue":{"value":{"entity-type":"item","numeric-id":3771607,"id":"Q3771607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$6EFFFDDC-D308-42C3-817F-8903EE9DDC13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$AAD60F57-81EF-45ED-AB9D-DE29FC7C807F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec62482a6f1abfd15d9d0aa6d0ca02f4b7a14835","datavalue":{"value":{"entity-type":"item","numeric-id":1095658,"id":"Q1095658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$DFC217CD-E4B6-466D-9DF2-D833EF3A1E9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c4f599c7e80cc4a63e588fa61d4f84934315f3e","datavalue":{"value":{"entity-type":"item","numeric-id":4154064,"id":"Q4154064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$FAB0F6AB-22AC-4CB4-AA6F-7C7C973057CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90edd91337b9f75f05ada0540fd29f2958b60727","datavalue":{"value":{"entity-type":"item","numeric-id":1062456,"id":"Q1062456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$8B5CCEE4-C35B-431F-A037-F6171184018F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3b7f421571a2d71ea5ce0028ff1487f50f83aed","datavalue":{"value":{"entity-type":"item","numeric-id":3753502,"id":"Q3753502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$01E141B2-16ED-4B16-9720-6E5E30AE4CCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104756$7EB3B2FD-FE2D-4895-B010-F44FFFE6EED7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"999fbbfaa4b099d782f722056f076ed78545fff1","datavalue":{"value":"https://doi.org/10.1007/bf02122548","type":"string"},"datatype":"url"},"type":"statement","id":"Q1104756$C07EE4CA-316C-4F2D-96BD-D7FA1C5385C1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cc9999e08bfa8ca2e4b7413d73772ff0302cd745","datavalue":{"value":"W2049327803","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104756$F471FD0A-4B03-4370-BC4A-2B43B2EEFD50","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88ff80cafa1cf91f4d28ebeddc1ac0134ed9e5be","datavalue":{"value":{"entity-type":"item","numeric-id":3357536,"id":"Q3357536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88f3a15840c187535363e2ea5dd56fb98f172e59","datavalue":{"value":{"amount":"+0.8517916202545166","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":"Q1104756$E550841D-425D-4269-9BB8-FCF8F1145EDB","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":"00774d2e392d702486d6b74f3eddae7d496838e2","datavalue":{"value":{"amount":"+0.8471927642822266","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":"Q1104756$4DD98B0D-DEBE-488D-BB82-E872C0CD50CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"188dd459af2ad7483f064c7fa961571afce79b19","datavalue":{"value":{"entity-type":"item","numeric-id":3034839,"id":"Q3034839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd1bc40fa825b7e0d3d10d5f1d4814a99874123a","datavalue":{"value":{"amount":"+0.8390110731124878","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":"Q1104756$03EAE884-4F83-40AD-BDB0-AAFD751CC50C","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":"37d512a31c0cc28054e8041de9531be755354392","datavalue":{"value":{"amount":"+0.8350182771682739","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":"Q1104756$68157E55-FDB5-451A-8A2A-998758A81733","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dafe265571253c63b6c711bccef80d5aa0eee0af","datavalue":{"value":{"entity-type":"item","numeric-id":1111396,"id":"Q1111396"},"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":"Q1104756$5A2422F4-9517-4F43-A90B-81191AD4A39E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A random NC algorithm for depth first search","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_random_NC_algorithm_for_depth_first_search"}}}}}