{"entities":{"Q685690":{"pageid":687539,"ns":120,"title":"Item:Q685690","lastrevid":63462303,"modified":"2026-04-11T13:20:00Z","type":"item","id":"Q685690","labels":{"en":{"language":"en","value":"Recognition of DFS trees: Sequential and parallel algorithms with refined verifications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 423584"}},"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":"Q685690$D8666DC4-F40D-4914-8BE2-E27419B31785","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee778cd7865c68666323526db2ee997c3dbf7a09","datavalue":{"value":{"text":"Recognition of DFS trees: Sequential and parallel algorithms with refined verifications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685690$86EBBCDC-C81D-463D-90C3-F2A26616D504","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"81c61914091c1d3658ae080f19b0d776c76169f5","datavalue":{"value":"0787.68081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$AA79E658-B82B-4287-B1B8-C87008F04664","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f37286a32fe6652c20eb70a4c7c642ebd6a6834e","datavalue":{"value":"10.1016/0012-365X(93)90375-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$BB7A978A-10EF-4E79-81D9-18D8127DF776","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d049f32d9c5057f44701109662e613026b41055","datavalue":{"value":{"entity-type":"item","numeric-id":216241,"id":"Q216241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$985A4CC8-54B5-49AA-93FA-785B12DCF698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c10055488937e86f40d3562527ec5d9ff3e51f99","datavalue":{"value":{"entity-type":"item","numeric-id":685689,"id":"Q685689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$26F7C20A-DF8D-41EA-9CC0-0F696BE17B55","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$44A9BDB0-0BBD-4E32-8DF4-187F7A403EC3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1a4582cf37b19337c7eae16fd67b6e107844c9e6","datavalue":{"value":{"time":"+1993-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685690$A3B9B0CF-1FFA-4867-BDB1-66BD4376A3FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1971a6e00bca16d0549acc1809e99eafa9265532","datavalue":{"value":"The depth-first search (DFS) algorithm is one of the basic techniques used in a very large variety of graph algorithms. Every application of the DFS involves, besides traversing the graph, constructing a special structured tree, called a DFS tree, that may be used subsequently.   In a previous work we have shown that the family of graphs in which every spanning tree is a DFS tree is quite limited. Therefore, the question: Given an undirected graph \\(G = (V,E)\\) and an undirected spanning tree \\(T\\), is \\(T\\) a DFS tree (\\(T\\)-DFS) in \\(G\\)? was naturally raised and answered by sequential linear-time algorithms. Here we present a parallel algorithm which solves this problem in \\(O(t)\\) time complexity and uses \\(O(| E|/t)\\) processors, where \\(t \\geq \\log| V|\\), on a CREW PRAM. We also study the problem for directed graphs. A linear \\((O(| E|))\\) time algorithm for solving it in the sequential case and a parallel implementation of it, which has \\(O(\\log^ 2| V|)\\) time complexity and uses \\(O(| V|^{2.376})\\) processors on a CREW PRAM, are presented.   An important feature of our algorithms, that we call refined verification, is that some of their decisions are endowed with proofs that can be verified with a better complexity than that of the algorithms themselves: In the undirected case, if the answer of the algorithm is negative then it outputs a proof for the fact that can be verified in \\(O(t)\\) time complexity with \\(O(| V|/t)\\) processors, where \\(t\\geq \\log| V|\\), on a CREW PRAM. In the directed case, if \\(T\\) is not a DFS tree in \\(G\\) then the sequential algorithm supplies an \\(O(| V|)\\) time proof for that fact and the parallel implementation supplies a proof for the fact that can be verified in \\(O(t)\\) time complexity with \\(O(| V|/t)\\) processors, where \\(t\\geq \\log| V|\\), on a CREW PRAM. If \\(T\\) is a DFS tree in \\(G\\) then the parallel implementation of the algorithm outputs a proof that can be verified in \\(O(t)\\) time complexity with \\(O(| E|/t)\\) processors, where \\(t\\geq \\log| V|\\), on a CREW PRAM. Hence, all the verifications have an optimal speed-up.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685690$73185899-B740-4151-91F0-9D8FA64E0E44","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$D7A0BCFF-5BBD-4FA6-99CE-D83DD6A864B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$98F9C71E-E11C-48A9-90B2-BD061AF165D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$507BCED6-CE87-4D6B-BC4F-245B990A4392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$3FFD3B8D-4C43-47FD-9093-404410C6BE12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$8BA5AA47-0640-4509-9B2D-075854AFA332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$6C8F92C2-E0FA-49A0-A939-D51ED31853AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$0DDC95F3-6102-4D20-895D-2F15FAB250EC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5599a868da572a8dd8dc7df9fd437d6667a8ed8a","datavalue":{"value":"423584","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685690$10352673-53B2-4BFB-8C4F-E3D83CC70A97","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5ca7553590ed1fa1bc930967051ac059fc7cf9a","datavalue":{"value":"acyclic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q685690$88CE9F1D-A899-425E-B9C0-F65FBC664714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff7bf11626141f10491819543bc6e69eb57efdf3","datavalue":{"value":"depth-first search","type":"string"},"datatype":"string"},"type":"statement","id":"Q685690$6B9911DF-9E14-4321-B16A-DC24CAEBD9C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q685690$32F52341-7A3F-4F10-B416-E0100D159DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b079af57319b3249dcaabd69976a156ad809246c","datavalue":{"value":"DFS tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q685690$919DEC50-33B0-4BEE-AAB1-0C249E1DCB24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q685690$C3C2FF52-47CC-4786-AE7D-21492009587A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34f1528cd9548b088936bf54fdf77b3eb118e9bc","datavalue":{"value":"CREW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q685690$7895FB39-2556-465F-8514-6FF38935C61E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1587f4800a6a8c1d6f5ca3ea8ef278e1b378e09b","datavalue":{"value":"refined verification","type":"string"},"datatype":"string"},"type":"statement","id":"Q685690$A88CAE27-22BF-4F39-B0B0-EBD5AEFAA802","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"45048559eefa05e5e21c6d306ffd9a763129c162","datavalue":{"value":{"entity-type":"item","numeric-id":24801,"id":"Q24801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$A581B335-7C33-4A14-A6AB-9EDFBB397D9A","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":"Q685690$48237B27-4ACD-4FE8-8A8C-6C4DC2D1A386","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":"Q685690$3DD9AA19-8272-4813-862D-5F664F2C1F53","rank":"normal"},{"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":"Q685690$ADEC70E7-C5FC-4A6E-BFE6-0C4BB13D5027","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00d9ee0dcdf8442d977fb2b0e5d6a60f0f9d541b","datavalue":{"value":{"entity-type":"item","numeric-id":1062756,"id":"Q1062756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$37B2FF33-9768-4B82-BE4E-628B194B38BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$0D134DD7-79C3-4B27-B5F6-81A7A5E40ED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"995396fbb270b5d7959f08a1f06a1da58561d49a","datavalue":{"value":{"entity-type":"item","numeric-id":1105381,"id":"Q1105381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$0188BDF6-179F-40E5-AA6B-59EA889D1DB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1265334c97f9278fdebf22ec46b939a0e44b551","datavalue":{"value":{"entity-type":"item","numeric-id":3798262,"id":"Q3798262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$E6702DBF-4E96-482E-95EE-292169DE1080","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$EE340E9A-B0E5-4ECF-A956-90863B6E71F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$EA068D10-7D8A-4CA8-B457-B910ACAA1964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e7ab4288eac319ed3df02e927ce5bfd06384991","datavalue":{"value":{"entity-type":"item","numeric-id":685690,"id":"Q685690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$5D6CAEB4-D815-4A55-ABAE-86D6CB66A044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508894c78bd2770d073dbe57a0316a7e71f6bc30","datavalue":{"value":{"entity-type":"item","numeric-id":3890136,"id":"Q3890136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$84938947-12F8-4735-9A51-F246F330CAD2","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":"Q685690$D140AF1D-CC05-449D-B5FF-232AF2E77C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"949d747bc2fb3851a5122e58dd2dc09e2a9a2ca0","datavalue":{"value":{"entity-type":"item","numeric-id":1111396,"id":"Q1111396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$87BFD5A2-A042-4EC5-88E0-91C2F8D31BFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5837867e98a618d52ced5a6f2437b38b50f0adc4","datavalue":{"value":{"entity-type":"item","numeric-id":3823152,"id":"Q3823152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$2FEDDED3-A3E5-4432-9EA3-5A881C1FE67D","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":"Q685690$471B17CB-8E8E-4BF9-ADBA-46BE1FE41A18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5b400ed59b3fd9367827d347c7820afe0d6078d","datavalue":{"value":{"entity-type":"item","numeric-id":3219788,"id":"Q3219788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$89B42E74-A03B-4FA1-9972-03B95EB2F7C1","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":"Q685690$AB0782C4-31E1-4146-95F6-B9FBB7D87082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c5477e08259683f4f1214eab272881c214067b5","datavalue":{"value":{"entity-type":"item","numeric-id":3694710,"id":"Q3694710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$2FDD0FD4-12ED-4270-9FA7-128E0E28A882","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57ef3857062b7526f0053324aedc3e9d5ac4de1b","datavalue":{"value":{"entity-type":"item","numeric-id":3725546,"id":"Q3725546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$9C17EFC0-1B55-4DD7-A381-699B8D43B47D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7a9e60ce3d1cc32797da1f44ff0782a98e6210e","datavalue":{"value":{"entity-type":"item","numeric-id":1082819,"id":"Q1082819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685690$EB836239-4289-4B34-B67A-90CBE05E1A23","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3adac5ec990bf7a9ad6ff1fc86419f22030212f","datavalue":{"value":{"entity-type":"item","numeric-id":2087463,"id":"Q2087463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ac05d721408d4b0eb2e881b9db727f70c1f3890","datavalue":{"value":{"amount":"+0.9104295","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":"Q685690$69845EF9-2FDE-4F3A-A69B-50E01E0EAF0D","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":"4dc8cf8f27e6a74efaa7ec193974390fe7505ac7","datavalue":{"value":{"amount":"+0.86548686","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":"Q685690$1A341136-BB13-4987-8914-2BB4E4B8FD2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69935bc159b58e4595fdd74f661eaad432c46cd2","datavalue":{"value":{"entity-type":"item","numeric-id":2484297,"id":"Q2484297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff3ff137bcd26dd090636ce45a47ab57d7c286da","datavalue":{"value":{"amount":"+0.86341137","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":"Q685690$F74B2CC5-65FA-44BC-8AC4-CC292E699EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e85a7192237d6f405772358836615f11308058a2","datavalue":{"value":{"entity-type":"item","numeric-id":3219788,"id":"Q3219788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc484a439d4caad4f44bd38ad6ac3fa67899df61","datavalue":{"value":{"amount":"+0.8630574","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":"Q685690$A1046D1F-5C6F-4A34-99FB-5D7DA05BA5BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ae699a72a7b530daac4fa939037150f6792a0bd","datavalue":{"value":{"entity-type":"item","numeric-id":4997136,"id":"Q4997136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af19e47fa67b078e06b19a31c9128b8e78570161","datavalue":{"value":{"amount":"+0.8586364","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":"Q685690$FDEE2101-23F8-472B-A023-CE8D016EA499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f0215bebdfa3edeb8afc40d6af6697c694a16c2","datavalue":{"value":{"entity-type":"item","numeric-id":3637347,"id":"Q3637347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87f4b773ab10c2d2e359f31b66f77f186301f950","datavalue":{"value":{"amount":"+0.8554729","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":"Q685690$959AB4AA-D87F-45DD-B489-3E9CB9C39403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eebb7d45f34646e83790aa207e2f387bc3a138d9","datavalue":{"value":{"entity-type":"item","numeric-id":1178197,"id":"Q1178197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56088700ac6bc21707f947537e4a7f6c521c3586","datavalue":{"value":{"amount":"+0.85208917","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":"Q685690$9393BD12-988F-4161-9A78-B3B4BC154DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2de59a9144cb440fe17c35ade4d13579293683f8","datavalue":{"value":{"entity-type":"item","numeric-id":5039512,"id":"Q5039512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4f8f81fff88dcd078fface41627b39dc33cfa09","datavalue":{"value":{"amount":"+0.84885734","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":"Q685690$363FC4C5-5444-4755-BC15-F1C8A4AE8944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9ba4a0084c2f37d111150cca1aa407ebe6bd909","datavalue":{"value":{"entity-type":"item","numeric-id":911287,"id":"Q911287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00dec49d70e855d949f99d970d57b4a0af188a18","datavalue":{"value":{"amount":"+0.8479627","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":"Q685690$C019F3E3-D054-4114-AA4C-7D75C4A40F1F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recognition of DFS trees: Sequential and parallel algorithms with refined verifications","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Recognition_of_DFS_trees:_Sequential_and_parallel_algorithms_with_refined_verifications"}}}}}