{"entities":{"Q1110330":{"pageid":1121079,"ns":120,"title":"Item:Q1110330","lastrevid":42884187,"modified":"2025-07-15T17:12:31Z","type":"item","id":"Q1110330","labels":{"en":{"language":"en","value":"An improved algorithm for transitive closure on acyclic digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4072380"}},"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":"Q1110330$B5C15083-0E1D-416C-A097-14544CC41038","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"edbf8205f171f16aaacfb76ce5d0f9016a2c59cb","datavalue":{"value":{"text":"An improved algorithm for transitive closure on acyclic digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1110330$7F25D7DF-DE98-4436-A89C-ECB2A26699BC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e7dfb5f005e4124e2b11290ba83fa813e9d77ba7","datavalue":{"value":"0656.68047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110330$D455B548-0D43-47AE-95A9-FB12D30C7DBC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4216649a1e8c0ec0aaddbe87efe46840a0ef02a3","datavalue":{"value":"10.1016/0304-3975(88)90032-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110330$6F0609F9-AA31-463C-8EE1-5B8D59D080B3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"596041614ba6bf5feed3bca261bdd3a3c4c5933a","datavalue":{"value":{"entity-type":"item","numeric-id":673000,"id":"Q673000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110330$14ECD778-B3F4-4D86-979E-EB0612AD2F6C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110330$4F9DE6F4-11BB-44E5-88CD-E61CBA5C11D2","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":"Q1110330$E540717C-0F6D-4D53-B176-0B4FCF4A2282","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"347ed7a3bfd40c3e90e9aaa3b10749319b2a0f68","datavalue":{"value":"The author improves the time and space complexity worst-case bounds of \\textit{A. Goral\u010d\u00edkov\u00e1} and \\textit{V. Koubek}'s algorithm for transitive closure of acyclic digraphs [Lect. Notes Comput. Sci. 74, 301- 307 (1979; Zbl 0408.68038)]. Further, some expected complexity bounds are derived in a model of random acyclic digraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110330$AB75F73E-BAF7-4D88-BB31-E03FB68C2895","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110330$CF28D419-132D-4BAE-8FA7-F13D1894167B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110330$61DF3DCF-21E1-4009-9B84-08561FEA84B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110330$AF412A4C-3C77-4FCB-BCE6-ACEEEFCA522D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dd2399f4de5bb6d3349c11f3b50876eecf5e6e3d","datavalue":{"value":"4072380","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110330$BF1FD223-0D90-4D12-9F3A-551485D0F720","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2172c95850d4d639064ed3b544d88bb580faa4cc","datavalue":{"value":"time and space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110330$AFDDE0D1-158E-4CD0-A76D-0ED907D1667A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2efd6ca2e632b6ca823bc98fefd73c07a1f518da","datavalue":{"value":"transitive closure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110330$2DFF41AA-B37C-47FC-AB3E-8B84DC857158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60dc9db18579fe65c19dba5970438a7fb0c67433","datavalue":{"value":"random acyclic digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110330$4CF24280-FB33-4B78-BC8F-0FDF0724F33C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"532bbaac3e370e50bd6ddecca89db5cad8ecea04","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110330$F11EE6CF-1602-4214-ADBC-CFB01DD176CF","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":"Q1110330$11F2D3EA-1C88-45DB-BAA0-D0DBDE892859","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"136e0bfa9b7a1deb8394f6910343855bd778dce7","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90032-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1110330$8FD0194B-D60D-48D2-B926-05E5E0246463","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a9db1a3e0722166ca62724c50a33386fad56038","datavalue":{"value":"W2017139167","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110330$868A5182-7A97-4F25-833F-09D02B45EB8A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"706b7dfadcd56cec5d093fda1e7d188f9761a74a","datavalue":{"value":{"entity-type":"item","numeric-id":3931215,"id":"Q3931215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110330$4BD2F0CE-911D-42B8-A2BE-76771CBE7B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df73775b35fc18da9a022c1b7f6827a54469130b","datavalue":{"value":{"entity-type":"item","numeric-id":3338160,"id":"Q3338160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110330$6336D5B0-89B7-4F02-BD45-A725447C3F0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631afda92da774b2f35528b579855e622332ed35","datavalue":{"value":{"entity-type":"item","numeric-id":4065548,"id":"Q4065548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110330$B02F9ECF-49CD-447F-854F-0CD8583716F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11540e6f7ac79fde18f86ec42f427dcec14af967","datavalue":{"value":{"entity-type":"item","numeric-id":1057061,"id":"Q1057061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110330$424214A2-F290-4FDD-8CA7-46967560B8BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e1151ce44263b02c103d481f0dbae5f699b8423","datavalue":{"value":{"entity-type":"item","numeric-id":4195940,"id":"Q4195940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110330$15056AB1-1BB4-4105-A9A4-AEFA1B579D8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b870ff096cd9b7374b71a9c8fe8f62feec4207","datavalue":{"value":{"entity-type":"item","numeric-id":3219752,"id":"Q3219752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110330$81D06228-FD65-4CB6-B216-53C58B9DC02E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c26ef026f6404f716a5871aaf7429f1fe60933a","datavalue":{"value":{"entity-type":"item","numeric-id":3727385,"id":"Q3727385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","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":"Q1110330$E32CAA2F-8409-4520-B447-10251538E16D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d56c62c2ee128ab3cd63f87537a5c2c86a9504d","datavalue":{"value":{"entity-type":"item","numeric-id":5365129,"id":"Q5365129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1137df84faf05517373b2a8a37acd083aa0613b","datavalue":{"value":{"amount":"+0.9015766","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":"Q1110330$FD4E2007-1B32-465D-9D04-7603DF42C3B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"496a2c887248c5d8d5e1d0dbd92b687e890b8185","datavalue":{"value":{"entity-type":"item","numeric-id":1603584,"id":"Q1603584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46e05504c3de384633b09865c97bca464e57c77c","datavalue":{"value":{"amount":"+0.8944773","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":"Q1110330$E9D1E551-CE4C-4001-AB79-3942C68A1105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b25296290f8ff0979d03f0331a8580bacc8fdc59","datavalue":{"value":{"entity-type":"item","numeric-id":4854001,"id":"Q4854001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a45d5021964dccbe3da024759b63f14865fc91c9","datavalue":{"value":{"amount":"+0.88956183","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":"Q1110330$F0129842-5E29-405D-91B3-31A4900CB726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efddd26340c05d3429a9ab5484479a99287de954","datavalue":{"value":{"entity-type":"item","numeric-id":1124350,"id":"Q1124350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36e35402aba775d6ecc83af6b5579181248d8583","datavalue":{"value":{"amount":"+0.8844303","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":"Q1110330$2182399E-F27F-4AA9-B8A7-376F3AED864C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"980a98f239f652553f3c8ce74bf71071d22a3ad5","datavalue":{"value":{"entity-type":"item","numeric-id":5269373,"id":"Q5269373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc16f4965ec5c7581db89142c01efc256fd3866e","datavalue":{"value":{"amount":"+0.88293004","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":"Q1110330$CEE77A73-72E0-4A8A-8D21-D6A117A92281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17d5155c956245496a35b0f6dc7f8572b1cbcc94","datavalue":{"value":{"entity-type":"item","numeric-id":5890868,"id":"Q5890868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94a5642c996f2bff278bbdb799943ac285dbcc11","datavalue":{"value":{"amount":"+0.8829158","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":"Q1110330$205913C5-A689-4A8C-BCA3-14DD4E85FFC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0d62423f9d34b40667fe3444f7ad91e1ecf80d6","datavalue":{"value":{"entity-type":"item","numeric-id":5917499,"id":"Q5917499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94a5642c996f2bff278bbdb799943ac285dbcc11","datavalue":{"value":{"amount":"+0.8829158","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":"Q1110330$D5576619-5480-4EE5-8506-44D9004FD516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a7493187d3761bb2560894457ca4dfca087e8a3","datavalue":{"value":{"entity-type":"item","numeric-id":5269272,"id":"Q5269272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acc8709f00140d8f84a1613326dcb9a93804c9a4","datavalue":{"value":{"amount":"+0.8799841","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":"Q1110330$CD09CB70-2BFC-470D-B789-B4189C4BB91B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1110330","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1110330"}}}}}