{"entities":{"Q1110342":{"pageid":1121091,"ns":120,"title":"Item:Q1110342","lastrevid":66452394,"modified":"2026-04-12T10:10:17Z","type":"item","id":"Q1110342","labels":{"en":{"language":"en","value":"A linear-processor algorithm for depth-first search in planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4072402"}},"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":"Q1110342$58D35A9F-6E08-4683-89EF-F4E5A35EE2F7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"833cec36fe400023831ae625da1351dda9a0a598","datavalue":{"value":{"text":"A linear-processor algorithm for depth-first search in planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1110342$FCF01062-EC54-411C-B64B-9CD7A6CD7B0F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d0500dea3454ca2311e8926ca498d8b0542d6626","datavalue":{"value":"0656.68069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110342$0A295144-DD79-4315-A304-D25DF85A94C2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b107f1c3b9c294fc31f8e18da658914961844f79","datavalue":{"value":"10.1016/0020-0190(88)90048-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110342$1AF5A99A-D4AE-4189-A653-A05A243652C2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"74e17aa93cc511cb5322696dc585c8d315482910","datavalue":{"value":{"entity-type":"item","numeric-id":1110341,"id":"Q1110341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110342$3AAB9311-1B93-4E4E-B3E8-B27A236C614A","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":"Q1110342$C0DD301D-6D0D-4005-81B6-E0CCBAF50297","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":"Q1110342$9866CE32-F6C3-43AD-A9B2-E759169A0EB6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5b00c0a824be8752b62c1885cc86eb1be4de745d","datavalue":{"value":"https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1634&context=cstech","type":"string"},"datatype":"url"},"type":"statement","id":"Q1110342$BD0576B5-A12D-4BB5-9D88-40DF0AD2C247","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f902ba6f6bdb1b943d0d4cb9d2383f76a00a3902","datavalue":{"value":"We present an n-processor and \\(O(\\log^ 2 n)\\) time parallel RAM algorithm for finding a depth-first-search tree in an n-vertex planar graph. The algorithm is based on a new n-processor algorithm for finding a cyclic separator in a planar graph and Smith's [\\textit{J. R. Smith}, SIAM J. Comput. 15, 814-830 (1986; Zbl 0612.68059)] original parallel depth- first-search algorithm for planar graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110342$1A35A948-F85D-499D-8E0A-BB6D77D27AC1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110342$8E2CCE18-8F53-4271-BC0F-10548C82AE07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110342$CBF0A315-4321-460E-B49D-ECC78D181349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110342$09647097-40A7-4D1F-A22C-157B102830C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110342$33B48B69-163C-43B4-9916-EF93DF9D4466","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e42a72f215f3549e77fd4148e0aecf015a9ebc8","datavalue":{"value":"4072402","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110342$9B0EFA47-457A-4194-95DE-4759BE1C4887","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110342$7A806A19-9861-4A6F-AAB0-3EC058422DF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96a8ef39b1a2b3f219d1fcbe87b9f4e14a11a9fe","datavalue":{"value":"cyclic separator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110342$2C46ABA4-3F45-4C76-A6D4-A887F4EFCA47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"952a8a56519402d383d63bdd5985e0123ef2349c","datavalue":{"value":"depth-first-search","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110342$079B46FF-388C-459B-9719-0420B7E81C17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110342$4C6DB0C5-F44F-4822-8733-EBFCD159C8C5","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":"Q1110342$77884F95-FC95-4F5A-B2E4-0A7F244B8D9E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"454992c11a6c33ece3dfed0537b8973fbd4dcf41","datavalue":{"value":"W2170132497","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110342$6674C8B6-5DA7-4A8B-9B57-C74D8E00C21F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110342$CFF0BF3F-0302-4779-9638-DA7FBDFAF687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2bd35d34c8cb4660ca6ae9b0c6b460814b14576","datavalue":{"value":{"entity-type":"item","numeric-id":1082818,"id":"Q1082818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110342$6D3B8AEC-A500-4670-956E-85FB5751881A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110342$A3574BE0-1133-4CE2-B829-FEF750098512","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":"Q1110342$A822564E-2756-4AA5-A7F1-D59C758B5BC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07b3023ab2e96c7839c0565934faddc8d14acbd4","datavalue":{"value":{"entity-type":"item","numeric-id":1085169,"id":"Q1085169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110342$02AEDF06-34EE-4E87-913A-5969FD5D4363","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":"Q1110342$5D7A9D5B-3030-4638-9FAA-7F17826DE443","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":"Q1110342$C7E62F13-ED30-45B0-B59A-17847F74E902","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":"Q1110342$A588807B-953B-441D-A169-CFF8148430EA","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":"Q1110342$8B9372DB-B3B1-4FC0-A69B-CB930CA5C21E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a6bb84ed63e3fc8fe28c0599a7a28ad0bb4690b","datavalue":{"value":{"entity-type":"item","numeric-id":3216652,"id":"Q3216652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110342$95959E07-8624-482E-9E8A-F59260219E19","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":"a398007e04a7b0a5bb089d570003897c2108b02b","datavalue":{"value":{"amount":"+0.9145225882530212","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":"Q1110342$BB904C64-0FEC-4669-9D4D-C53A2036B003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15adf48044170f51bbe2be0fd79300e0c87003ea","datavalue":{"value":{"entity-type":"item","numeric-id":5060132,"id":"Q5060132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc5f211352c432f25f967d22a027c2f400c2c43f","datavalue":{"value":{"amount":"+0.9053702354431152","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":"Q1110342$7DABB0CF-C5AF-42FD-9662-B2AE8067963A","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":"255816e246e4f6e89b78dd0c9c844dec15a5041f","datavalue":{"value":{"amount":"+0.899543046951294","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":"Q1110342$FE949C56-7862-4C6F-B944-07C8D4C75D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"683558f65ee28addbbff1e08fdfcacc0cd7afe29","datavalue":{"value":{"entity-type":"item","numeric-id":1900892,"id":"Q1900892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba547d89499ebb9de890c04f5b1b083eca1aff8e","datavalue":{"value":{"amount":"+0.8912252187728882","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":"Q1110342$77434B84-FAAE-45D9-BF7F-06C591C79C40","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":"7f2ab55c939b513d657401ba6f8f67ada63a97a1","datavalue":{"value":{"amount":"+0.886016845703125","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":"Q1110342$E1322DDD-4FE7-40E2-92CD-D1B5C2CE8C4B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linear-processor algorithm for depth-first search in planar graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linear-processor_algorithm_for_depth-first_search_in_planar_graphs"}}}}}