{"entities":{"Q2149103":{"pageid":2159846,"ns":120,"title":"Item:Q2149103","lastrevid":54351884,"modified":"2026-01-26T16:42:54Z","type":"item","id":"Q2149103","labels":{"en":{"language":"en","value":"Fault tolerant depth first search in undirected graphs: simple yet efficient"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7549529"}},"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":"Q2149103$5FD0D1F5-F27C-4F39-B615-65A69B173101","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8c5bbbec052ccb44928745294b55f846d7b92de0","datavalue":{"value":{"text":"Fault tolerant depth first search in undirected graphs: simple yet efficient","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2149103$1A4DF5FE-1680-4312-B55B-A7436BE436F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02894431326e03d5b0b000bcc376186cb61245a9","datavalue":{"value":"1502.68206","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2149103$BBD47E15-A4B5-405F-979C-1EFED1E4F162","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"613801e34e3a60f4d110f7cc5838aeaa5c99898c","datavalue":{"value":{"entity-type":"item","numeric-id":666656,"id":"Q666656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$CD06A7A3-B688-4310-8FF2-E2461C4E1E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"428b89c6ebf109337a248470d07eca2bb7b7ec73","datavalue":{"value":{"entity-type":"item","numeric-id":2149102,"id":"Q2149102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$15A7EC90-C480-4D37-B5E4-5157AF536231","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e46b23a36f430a10c3cd6d064e3dec0939752006","datavalue":{"value":{"entity-type":"item","numeric-id":264346,"id":"Q264346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$3728FD1D-AE94-465B-8F2B-BF6D92C2C48C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$3BCABDF1-7D28-4925-9EEF-A6B703AA01DD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"42133c80abded9eae6bd11bfdbca607bf0fc1dc3","datavalue":{"value":{"time":"+2022-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2149103$65168445-0FA8-45B6-9605-DAFC44F81A19","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b69e61307038a8e612dc7ab85b20789caa5d06f5","datavalue":{"value":"The paper adresses the problem of computing a depth-first search tree in a graph \\(G-\\mathcal{F}\\), i.e. a graph \\(G\\) from which a set \\(\\mathcal{F}\\) of elements (containing edges and/or vertices) has been removed. In other words, the goal is to provide a DFS tree of \\(G\\), even in case of failures (corresponding to \\(\\mathcal{F}\\)).  The paper presents an algorithm that solves the problem, which is (as claimed by the authors) ``drastically simpler'', conceptually and implemention-wise, than the previously existing algorithms, while competitive in terms of running time.  Although claimed to be simple, the technical contents and description of the above-mentioned algorithm are roughly 15 pages long. It should be mentioned, however, that the authors took special care of motivating the problem, summarizing the main results and positioning their own contribution during the first five pages of the paper (Section 1) in a way I found very convincing.  All in all, thanks to the authors, Sections 1 and 2 can be easily understood by the interested reader, while it takes more attention to follow the remainder of the paper (technical contents), which is, however, well described and illustrated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2149103$A622C504-6BAA-4CA1-9848-38552B13D230","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3e3d71b48f3b9d9ad4587d8a3dcefa9681c4ac88","datavalue":{"value":{"entity-type":"item","numeric-id":214959,"id":"Q214959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$005C8646-A383-4EF7-A9DF-442683B5A597","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2149103$AE5FDECC-3600-4988-9956-F056D6EE9F78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2149103$A0790C26-B827-49D4-875E-0B56DFA6F31B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2149103$5503EDF3-4860-4988-BEE7-65607916E17E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2149103$2A52AFF4-A768-463D-941A-6A7CB3C9DD81","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ead66415fd0ed834a3ada5bce94e139a7da1ed2","datavalue":{"value":"7549529","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2149103$FAD0D6C0-515D-49B6-95CE-DB5593C9E39B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7aa00a4c4635da3e1a8927a353052773fcbd5326","datavalue":{"value":"depth-first search tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2149103$C1A7B100-E37F-4C82-8F2E-B1C85DFBBA5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b01b02968c48df9f6d634df64bea355af4ca03","datavalue":{"value":"fault tolerance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2149103$869EDD04-2C1A-4FF4-9C5F-4DA221C7A708","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":"Q2149103$0EDAABC7-3D57-4F3E-9EB3-C263C5E5F4F2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8eab957c8c9960b69ec92499f544ee841e320d61","datavalue":{"value":"https://doi.org/10.1007/s00453-022-00947-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q2149103$3E0367ED-7F47-4FE6-A83C-3DC304BE6B12","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"133d8f734a486aa5b5b404003d4ceb6ad547d009","datavalue":{"value":"W4214576505","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2149103$04AA613F-5F62-4207-8DEA-96FBCBF0AA62","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9c9a6d8c42b2d17ab79342f5a604a01dbd950b1","datavalue":{"value":{"entity-type":"item","numeric-id":3034839,"id":"Q3034839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$4D839811-0DF9-4256-87D0-F42A25347CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"652feff3ca2d3839c71b338be75f895036109373","datavalue":{"value":{"entity-type":"item","numeric-id":4575631,"id":"Q4575631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$3ABB2B50-B255-4BD9-9B48-C0BB28B0CD0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"318a26ead786ad96f3a26ba51a5af8551e654037","datavalue":{"value":{"entity-type":"item","numeric-id":2946380,"id":"Q2946380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$24B380BF-9B5D-42CE-8E45-37C04D428EB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c906ffb0da532dd29ff95dd7b679fcc58c2fa988","datavalue":{"value":{"entity-type":"item","numeric-id":4607876,"id":"Q4607876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$A56A3825-D2D7-474A-84E4-1B2BC95C09EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5371dfbc3a1aaf525291c9c6b25d9cc78b827ff2","datavalue":{"value":{"entity-type":"item","numeric-id":5092428,"id":"Q5092428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$3EB6698B-9570-4FBB-B11F-663769CF06A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48254f2c3b66f5c12da8ef537f9130d55b9a5de7","datavalue":{"value":{"entity-type":"item","numeric-id":2408922,"id":"Q2408922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$ABBA5B6B-E373-4901-8FCE-A6A4066D4C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd247d2f8d8a240f75bc7581457c447f9aa6aafe","datavalue":{"value":{"entity-type":"item","numeric-id":5172703,"id":"Q5172703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$47BDA245-679F-47C0-B83E-5D66A33C001A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6149736985cab44313f18807011ab51fb679ac88","datavalue":{"value":{"entity-type":"item","numeric-id":3579222,"id":"Q3579222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$08EDDAA1-A30A-4D11-BA38-745B56541C95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76ce173cdd6420ed78061b92000307f2e179c306","datavalue":{"value":{"entity-type":"item","numeric-id":1099957,"id":"Q1099957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$D70703AB-0933-4E34-B1DB-A1B78F745C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b86141b59682fc8b02fe1b41ab7e33c72578e0e","datavalue":{"value":{"entity-type":"item","numeric-id":5390599,"id":"Q5390599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$6DA0AF01-B97B-4315-82D0-9E5795327427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"422925608f3db546cbd7c77584c4bab362a8c68d","datavalue":{"value":{"entity-type":"item","numeric-id":5116480,"id":"Q5116480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$F8B4CC95-CE75-493C-A6A6-455E8057D242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cbbbdc00f82adc1b7bb4e5a78b2e4a8038b3a43","datavalue":{"value":{"entity-type":"item","numeric-id":3532564,"id":"Q3532564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$B0BFD80C-9578-47B2-A7B1-7C42482D2184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fc29baa395505e6b4a5622e6f517399614d2749","datavalue":{"value":{"entity-type":"item","numeric-id":2405295,"id":"Q2405295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$2E458FAF-3520-4A4A-A239-AF2037C9330D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f02946b4153ac50fac077af70130b7671852fb30","datavalue":{"value":{"entity-type":"item","numeric-id":286984,"id":"Q286984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$973A267D-2E2E-4BD1-BCAE-4CEC3D490763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0cae3e1da26d4eea98442cf5f2d54a6c9b26db9","datavalue":{"value":{"entity-type":"item","numeric-id":1578392,"id":"Q1578392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$A87F3ACB-5621-40DA-9958-7E6CE31173C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a0c9470c7f41a4963647da6186e90862da683e2","datavalue":{"value":{"entity-type":"item","numeric-id":4471381,"id":"Q4471381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$3FF2C365-3E83-4A55-BC9C-1B6C287DF5A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"226c58ef3bb5304e8c7a32593f076d32d825a7fe","datavalue":{"value":{"entity-type":"item","numeric-id":2312405,"id":"Q2312405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$4206A24E-C2B1-4573-B234-FF0550AB7E12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7b76c498f5c4968b18e0a5cf8a7bb4513c31822","datavalue":{"value":{"entity-type":"item","numeric-id":1838310,"id":"Q1838310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2149103$D71B3986-115C-4001-8F3B-9DEDABEC8174","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":"Q2149103$A4400C5B-EF88-4152-A160-E7309BED38A2","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":"Q2149103$53909B16-633B-45DB-97C8-EF899ADA6A13","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e6675ce2b86603a9fe8e822e41338ef8ecfc5015","datavalue":{"value":"10.1007/S00453-022-00947-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2149103$459E7DAE-5377-4391-AEFE-A1E3046A90C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcc9972b84aa7c2d4adb75ee9afaf8e01c434766","datavalue":{"value":{"entity-type":"item","numeric-id":5232328,"id":"Q5232328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4762fbc69f8987acad88c970887cb6939403ac6","datavalue":{"value":{"amount":"+0.785773754119873","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":"Q2149103$1F0264A5-50E6-4B8A-9784-B1E4EA4813DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e64f79cadd5cf7c3397ba4a3718a55bf56bf80df","datavalue":{"value":{"entity-type":"item","numeric-id":1664162,"id":"Q1664162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20d19a22e2dd0532f72876dd7c2a8dc128f1d145","datavalue":{"value":{"amount":"+0.7798877358436584","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":"Q2149103$28239F7B-8E56-4D55-BC21-0593B9CC5280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c42aee5bf108f32a5f3ed2bb01643724e384823b","datavalue":{"value":{"entity-type":"item","numeric-id":5116480,"id":"Q5116480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53ef3f18e94c0cf9c7cf260499fbcca03a92aa1d","datavalue":{"value":{"amount":"+0.7696128487586975","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":"Q2149103$52044D22-10F9-4F55-9563-3CD49A4DD4F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80e4667a90355e782d7c792d1ae409a462ec984b","datavalue":{"value":{"entity-type":"item","numeric-id":1062756,"id":"Q1062756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4d44a72186024af70aa27016963a2369cc49fff","datavalue":{"value":{"amount":"+0.7682479619979858","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":"Q2149103$A068D878-9317-420D-86D8-21603FDF492A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a2d32c03ec01264ce315408d6023390713400c2","datavalue":{"value":{"entity-type":"item","numeric-id":294748,"id":"Q294748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad3ca2a5af375b8b32d07a4ce993130dfd783d50","datavalue":{"value":{"amount":"+0.7626174688339233","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":"Q2149103$BCDCDE03-FC0F-4444-B81E-3376D27EE39D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2149103","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2149103"}}}}}