{"entities":{"Q1115184":{"pageid":1125933,"ns":120,"title":"Item:Q1115184","lastrevid":49242463,"modified":"2026-01-06T20:20:53Z","type":"item","id":"Q1115184","labels":{"en":{"language":"en","value":"Finding paths and deleting edges in directed acyclic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4085019"}},"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":"Q1115184$2E7A3C6B-148C-4FD5-941C-4257B5DF0E0D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d34f5a935f0f8d4e9af6894eb09a020380c69118","datavalue":{"value":{"text":"Finding paths and deleting edges in directed acyclic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1115184$2778FA1B-D7F9-4D4C-95F4-AA84A417FBE4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d82815118e9be22690eef69e298298e99e6699d5","datavalue":{"value":"0663.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115184$0F45077A-091E-4373-8899-89BF8F7E6749","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"787544e913787bbd8273cdf4189a8faaa6d83d23","datavalue":{"value":"10.1016/0020-0190(88)90136-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115184$0FEEC86F-39DD-445E-BBE9-3D708531EAA4","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":"Q1115184$BB914A21-712D-4F6A-A458-001FB45B2E71","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":"Q1115184$1E07C734-D161-4A57-BE97-0ABA1441DC7D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6954e7ca62b17a93fbfe5908fcb2c926518dab54","datavalue":{"value":"An algorithm for path searching and edge deleting in a directed acyclic graph is presented which realizes each searchpath operation in O(\\(\\ell)\\) time, where \\(\\ell\\) is the length of the achieved path, and any number of delete operations in O(mn) worst-case time, where m is the number of edges and n is the number of nodes. The algorithm requires a data structure of size \\(O(n^ 2)\\) which can be preprocessed in O(mn) time. This seems to improve previously known algorithms, which however handled the edge insertion problem also.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115184$3A03712C-3883-4EAC-BF1D-D3FB5E815CEB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115184$9CC2779F-A716-410B-B14A-9754FA975B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115184$62E8CD1A-ED0A-41A1-B163-7F7C92E6C499","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"730eb2e2516437c09871931953d90d3a90d38f57","datavalue":{"value":"4085019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115184$E992DDB6-2091-46B1-98E9-0175F98E7436","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"400399d734143d2aec1138d508fe745e46265d45","datavalue":{"value":"path searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115184$EFA48456-A205-4825-9F47-008EA133EFEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d8094f323ebc85a2c06c9abd2f86c88f2224f05","datavalue":{"value":"edge deleting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115184$116155F3-692B-4361-A70C-DC6B79E4BF31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b30413bdc80736aeecdc7f80229ac89c0446304","datavalue":{"value":"directed acyclic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115184$6332864B-B7CD-4332-B124-CF6B658311A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c25bc710e4a99b4ad5c06b7d722ebbdb9259ca1e","datavalue":{"value":"data structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115184$106EA7D5-8542-427D-9EA0-0D3E760FA935","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"195c9aed1bd89c35e1df78e6f20597fcce0f59e3","datavalue":{"value":{"entity-type":"item","numeric-id":270020,"id":"Q270020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$05813A80-FB47-4195-8E8A-A95405307786","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fc8522c6547fe483c0d1ae4eec1b8d9306e5db1","datavalue":{"value":{"entity-type":"item","numeric-id":290243,"id":"Q290243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$184D3BF7-0ADF-4439-80CC-DAF218B3562C","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":"Q1115184$1BAFA397-8D1B-4C40-85C8-0D4A2AF191D9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c5d10e033bec58b18cc71801ff6ffebdcc329c81","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90136-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1115184$8B9E68C3-22CD-47F0-9BE4-FCD0DDD40C2E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"94d83108003be921cc6b26084bf0cb7ca81ea5a3","datavalue":{"value":"W2037034819","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115184$EE98F0BE-D05A-47E9-816C-9BA1474C2B7E","rank":"normal"}],"P223":[{"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":"Q1115184$D3567270-A841-4389-9023-F891FBBF6DF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6db42059db76cc745bf7cd33296cd44ef823c3a8","datavalue":{"value":{"entity-type":"item","numeric-id":3679232,"id":"Q3679232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$F65610C5-DE3B-4762-98D4-275E1DC8ABFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f2c2e2aabc37308f5d7abda56807c04ca8da5b9","datavalue":{"value":{"entity-type":"item","numeric-id":3902517,"id":"Q3902517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$326593C1-F1F3-49C9-B9F7-231B25E64963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c0a13a8417673f45e28aa7499e1e7b9d7bfca27","datavalue":{"value":{"entity-type":"item","numeric-id":3694711,"id":"Q3694711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$E54B1C34-88D9-45E3-9496-12D08FD5966B","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":"Q1115184$5B960D99-1911-4F71-A5CA-606B94722B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa908eeca5ab977342dab5767d79cc2223d5cbbc","datavalue":{"value":{"entity-type":"item","numeric-id":1051432,"id":"Q1051432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$94FFBE0A-2CE9-4CBE-868D-94B3CAB0178E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f44150bf5f8b9a18037b1fe7ce1cf57190c903a","datavalue":{"value":{"entity-type":"item","numeric-id":1099629,"id":"Q1099629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$EF469746-B676-4851-8A6B-32FFBEE23343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40a553d7b2714cb381cc91507113fb9f26fcb8f2","datavalue":{"value":{"entity-type":"item","numeric-id":3813313,"id":"Q3813313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$F3DD474D-A5FC-431D-AAB8-7E85F58ED424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2610c7d27ba8314328868947db0889cd433897","datavalue":{"value":{"entity-type":"item","numeric-id":3685214,"id":"Q3685214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$4C30DEE9-6A37-40AB-9FFC-99784359C83A","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":"Q1115184$5A3A9495-0482-4320-8931-EEDCA33F87DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6373287f1fcccf64ae7027e1e67254a951f67b26","datavalue":{"value":{"entity-type":"item","numeric-id":3795247,"id":"Q3795247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$1240BCEC-D48E-4634-8D80-B73438FC8B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00910816ba034b6655b7a47d13d1206cc1d40ae2","datavalue":{"value":{"entity-type":"item","numeric-id":3735083,"id":"Q3735083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$2EB4A4F2-CED2-4175-8A19-4AF2655984FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e9366c82f8a71633f567b778add8be59a85724d","datavalue":{"value":{"entity-type":"item","numeric-id":3769963,"id":"Q3769963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$0A90B886-4FBC-4A8E-AC50-9057413B6E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"796e8de54796a3c9407cc7428aff3ebfdd322e19","datavalue":{"value":{"entity-type":"item","numeric-id":3783603,"id":"Q3783603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115184$8D4F2373-F178-4CE2-884A-E99766710C84","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"36a246bb85434dedbcd319fd25ffe1adbe91013d","datavalue":{"value":"Q61609677","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115184$004D6F0E-C99C-4654-A96F-0254274ED9ED","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e47e0d44f9a944f92b560562bd7d5a994cf8525","datavalue":{"value":{"entity-type":"item","numeric-id":4894957,"id":"Q4894957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a956a3e9358b8a69a30c8b64387746d2187d4d56","datavalue":{"value":{"amount":"+0.8029171824455261","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":"Q1115184$841E7E4E-2739-4304-BED1-217EFB0495F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0308cd1a09e7ca1fa40eed4339a00a0dafd9efd6","datavalue":{"value":{"entity-type":"item","numeric-id":4500615,"id":"Q4500615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0409916dd9aab2ec51f274754eaeb0f916521db6","datavalue":{"value":{"amount":"+0.7572235465049744","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":"Q1115184$43C4B5D0-B42E-478F-B9A8-B3B051BC669D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c296b0061e0aaf626d312ee2bb7242e0b388619","datavalue":{"value":{"entity-type":"item","numeric-id":4419764,"id":"Q4419764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86c4b6f933acb2b368b94292b4728aac715e3102","datavalue":{"value":{"amount":"+0.7561340928077698","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":"Q1115184$60CABA01-92D2-4EA9-A07D-F810D291B648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1866886bd4492a7ef6f917427c402bf565006480","datavalue":{"value":{"entity-type":"item","numeric-id":3532572,"id":"Q3532572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef5663283d21c62ffc5fd4c0a2772ed0061762c3","datavalue":{"value":{"amount":"+0.7510960102081299","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":"Q1115184$5285867B-75EE-4322-AF15-65D0CCA798E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92be433f87f442726da1e4f239f2fd8ad1e9f5ad","datavalue":{"value":{"entity-type":"item","numeric-id":3507767,"id":"Q3507767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69e1004976541e16f1b499998d58579641404d81","datavalue":{"value":{"amount":"+0.7463874816894531","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":"Q1115184$4AC96371-E925-42B8-B461-A31B940FB707","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1115184","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1115184"}}}}}