{"entities":{"Q1062456":{"pageid":1073208,"ns":120,"title":"Item:Q1062456","lastrevid":66061482,"modified":"2026-04-12T07:16:35Z","type":"item","id":"Q1062456","labels":{"en":{"language":"en","value":"Depth-first search is inherently sequential"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3913695"}},"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":"Q1062456$20D983C4-F02E-4E34-A78F-371EF692CF5E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eaf3a051b255cafc62fc9d485d4f9d7518e372b9","datavalue":{"value":{"text":"Depth-first search is inherently sequential","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062456$9CDD361C-CA58-43B7-8CF0-3A693F96A1BC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c5b4150e94beb1ef39ed86ff96eb83bb2386fb7c","datavalue":{"value":"0572.68051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062456$13ECF9F7-19B8-497D-B010-578AB031EF84","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0d9fcb25b35197a563a826b1d4d7e4373c512500","datavalue":{"value":"10.1016/0020-0190(85)90024-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062456$494816B2-E2D2-4EE3-A192-C4833FE98171","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3cdf21d0e331a47790f86a0203b4b15950c2a72f","datavalue":{"value":{"entity-type":"item","numeric-id":537850,"id":"Q537850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$05DC9457-B0FE-4063-9562-F61151E5C7C1","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":"Q1062456$5D77AF4C-E58D-41FF-AC5E-B600F566D7D0","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":"Q1062456$955D1675-5FA9-4F03-A500-D1F319212C2C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a0a7eae29b2ea4f00f5786b09d549915d70c69c","datavalue":{"value":"This paper concerns the computational complexity of depth-first search. Suppose we are given a rooted graph G with fixed adjacency lists and vertices u,v. We wish to test if u is first visited before v in depth- first search order of G. We show that this problem, for undirected and directed graphs, is complete in deterministic polynomial time with respect to deterministic log-space reductions. This gives strong evidence that depth-first search ordering can be done neither in deterministic space (log n)\\({}^ c\\) nor in parallel time (log n)\\({}^ c\\), for any constant \\(c>0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062456$EB8E093C-DE97-4EC1-BDF1-2078FB3D23F2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062456$73F048EF-663E-45A7-9005-079AC1C3D58B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2a7741654c1fbbbd73d2ef6a0eaf57adeb5db35b","datavalue":{"value":"3913695","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062456$D34A7D64-9958-4921-9568-53640B64BDC3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062456$32A88C2C-441F-47DF-A183-34A89AAB268B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e88137f20df4ae2c87a2fed93570723b282fa558","datavalue":{"value":"polynomial time complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062456$59EBC343-61C6-412F-8B3C-58704769065A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2cacaf8d0390b65047dd77c54eebb66b0f1790c","datavalue":{"value":"rooted graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062456$6C43FF93-61CC-4493-9FBD-307713E4D845","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":"Q1062456$E9FCDBDE-609C-4097-BDB9-106E736528AF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c45116411525a5efd1aa3d5ce84d26878e830ffb","datavalue":{"value":"https://doi.org/10.1016/0020-0190(85)90024-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1062456$640FA857-E28B-4AB7-91B0-6330317978F6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bb2aecf501ea7ba029fcc4c2b1bc0f0bbcf50666","datavalue":{"value":"W2085467310","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062456$00557D10-6E41-4C19-9AAF-64130F8ACCCA","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3904a7830e97ea74aad58b75a5f0bfdff3ac8238","datavalue":{"value":"Q55923944","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062456$C14F5A7E-9D66-4E2F-9068-66D4A616E76D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0445ca81f1046c8b5bea1a2062f174b139078383","datavalue":{"value":{"entity-type":"item","numeric-id":1217591,"id":"Q1217591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$B80C8337-F68F-4E7D-95ED-7E7A43BE5321","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12c6f50eb5a5939405c1877dfdfbe7a7d53f3f7f","datavalue":{"value":{"entity-type":"item","numeric-id":3944008,"id":"Q3944008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$C6C30314-893B-4650-BBCB-D245541B9719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18bf67666549968e21bcfc545117ac605c5708ff","datavalue":{"value":{"entity-type":"item","numeric-id":1255780,"id":"Q1255780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$50AD11E4-45CE-499F-A3B8-C77AB8084D4B","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":"Q1062456$63C9B293-1A64-45B6-916B-407D64232A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2628ffb9e59aa19553582ac944ed7dc8d827a3a","datavalue":{"value":{"entity-type":"item","numeric-id":5402548,"id":"Q5402548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$7C02C22C-440B-4D5F-8E69-FCD02B4CAB7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d53db4e61bfa2d597f0a53da172502701ac0503","datavalue":{"value":{"entity-type":"item","numeric-id":5402545,"id":"Q5402545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$DCC8B694-ACF6-440D-954F-E7A67C055FD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c858b89b9774cab823f151be95554a91f314d3ef","datavalue":{"value":{"entity-type":"item","numeric-id":1165000,"id":"Q1165000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$54193369-22A7-4754-A463-42BFC5F6B7F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$EC571E16-F4A4-4074-8742-C57092D21BE7","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":"Q1062456$0908262B-0ACC-4086-8BE6-F79FC748A924","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":"Q1062456$048A12E2-2FAE-4AEC-B46C-255A95EE0537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$44EEC814-F891-494D-86A6-CA043B9FA334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"373c65ef4069b52a23fe230e08a271e32f56a00a","datavalue":{"value":{"entity-type":"item","numeric-id":1235982,"id":"Q1235982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$B44FFD18-BA66-4A72-AADC-695D07AD8B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e472e71486639d0030dd63f9880bf07574170e62","datavalue":{"value":{"entity-type":"item","numeric-id":3769977,"id":"Q3769977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$61313969-0A17-4DD8-8FCD-585F8B527D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52a451237ce593e85222bec0df72697177925cb4","datavalue":{"value":{"entity-type":"item","numeric-id":3347295,"id":"Q3347295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$A1E37AC2-09B4-43BB-866F-1E900B3A169E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b3dce3552dfbea64412441f1ced1f652d688fa0","datavalue":{"value":{"entity-type":"item","numeric-id":3932299,"id":"Q3932299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062456$89D7F659-9B15-4493-AF9E-DACDAD5D8EEA","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":"Q1062456$53EE9470-F397-44C7-9E35-9EF6D05461A9","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":"c066c388b3a56584b006d555d4f62cf1af17f7a2","datavalue":{"value":{"amount":"+0.8276583552360535","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":"Q1062456$0F07F7FE-5E8B-4950-B234-755A85B18931","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":"1bcc26e2c3787733427cacf1490b44a38ef657aa","datavalue":{"value":{"amount":"+0.8121069669723511","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":"Q1062456$715F06B7-CB77-44BC-A2F9-1A6AFC2D0967","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":"0c8f6dfb2afb7b93b9640897b5e49e6b087a0a57","datavalue":{"value":{"amount":"+0.7988724112510681","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":"Q1062456$24DC24DC-CDA2-4C85-B4CD-95D69076EA1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3baa70217c982a685ed6506ff54a662aaffa50d","datavalue":{"value":{"entity-type":"item","numeric-id":3802639,"id":"Q3802639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a8d38f2dc98757ebafc56359a29c0639fa64072","datavalue":{"value":{"amount":"+0.7826219201087952","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":"Q1062456$F06F3755-5DB7-4ECA-8DF0-BC46CB6CEE02","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":"39ad08b81262012f667da727ecd864c5f741e419","datavalue":{"value":{"amount":"+0.7773572206497192","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":"Q1062456$3E3FADE7-B74E-43AE-8863-4C34CBCC6C6C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Depth-first search is inherently sequential","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Depth-first_search_is_inherently_sequential"}}}}}