{"entities":{"Q1124350":{"pageid":1135099,"ns":120,"title":"Item:Q1124350","lastrevid":42897588,"modified":"2025-07-15T20:13:04Z","type":"item","id":"Q1124350","labels":{"en":{"language":"en","value":"An algorithm for transitive reduction of an acyclic graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4112034"}},"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":"Q1124350$B8E56861-ADA0-466D-9E25-6FAA65882621","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"345acc7b712054753c75219abe8dddffce757a68","datavalue":{"value":{"text":"An algorithm for transitive reduction of an acyclic graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1124350$A92B46FE-1ADA-46E6-83BB-5DC56EA4E58A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a325229ddf656e36892aba59372fb534966c6233","datavalue":{"value":"0678.68061","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124350$01ED5990-D446-4776-9E3D-850F7CE7C25B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2afb7f39c777b7a65b0d2bf79bbaf05230d6ed65","datavalue":{"value":"10.1016/0167-6423(89)90039-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124350$F2FDB8BB-5AD0-4F0C-817A-9DDE04D07E3D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"87201105ab9aadf571db6479712327a7fc2e406d","datavalue":{"value":{"entity-type":"item","numeric-id":287253,"id":"Q287253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124350$1AB8CADE-F01E-47A0-A856-DE39AC511183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1f3afe6a1a62a4538b2439fef487959c710cf5c5","datavalue":{"value":{"entity-type":"item","numeric-id":685121,"id":"Q685121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124350$DD03F9EC-4487-4BC2-B0A3-4F00B9B57983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f7cca814c6c22ae0d80459c936151789f68dc2f1","datavalue":{"value":{"entity-type":"item","numeric-id":753490,"id":"Q753490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124350$3978CCCB-B537-4ACF-A158-29416DE34DF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cfc7989709b90be760866570fcad9e172d7ecfd3","datavalue":{"value":{"entity-type":"item","numeric-id":751840,"id":"Q751840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124350$7CFD8B70-D329-4010-A9D0-2EBE0402EE09","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4082512e7d3530b9726df691c7c28e9fec542a8c","datavalue":{"value":{"entity-type":"item","numeric-id":169675,"id":"Q169675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124350$BBDA32A8-F706-418F-BC11-9D4FB909D241","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1124350$1B5BE08F-DD0D-48F2-AA24-2501C6F9B91F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"971f9d23cfe0c02cfb34999a6e073a2011980b13","datavalue":{"value":"A simple \\(0(N^ 3)\\) algorithm for computing the transitive reduction of an acyclic digraph is presented. It operates by first computing the transitive closure and then removing in essential arcs. The correctness of the algorithm admits a short proof.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124350$99256AD1-A432-4F99-890D-8E2286702428","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124350$D417FFB4-DCDB-432B-8B13-9F8EB4C51285","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6cfd5881bc4187c959be463947fad05fab1ab67a","datavalue":{"value":"4112034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124350$EF2055C3-AEE7-4EA9-A997-64AC947ABC28","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2cabee9de5e5cee0b36f72b703f609ab0d77ab98","datavalue":{"value":"transitive reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124350$DDF7CA08-D386-4134-BE54-D3D1D5E93726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"298a551ef47c5b20057a4bfdb8bbc9e28d84ca03","datavalue":{"value":"acyclic digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124350$4F4C87AB-CFCC-46CE-B650-0B1FAED3AFB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2efd6ca2e632b6ca823bc98fefd73c07a1f518da","datavalue":{"value":"transitive closure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124350$1054AF7E-F63E-426C-9673-BE26468231EB","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":"Q1124350$2D7486C5-3D40-40FF-AA12-73F8087C2EF0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"06211e4b04d1400ac10fca715e2503e4a7f0837e","datavalue":{"value":"https://doi.org/10.1016/0167-6423(89)90039-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1124350$568260A1-74F1-4231-8EF3-133A8C8191CF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a81cafbfccc002d7598d7f6a186ab695d10043d5","datavalue":{"value":"W2113553164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124350$C1778239-B7DC-4917-9E8A-B496DBDFFFC8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26b86a683cd90ff3357d8f5f9968dc2516e7d79d","datavalue":{"value":{"entity-type":"item","numeric-id":2736119,"id":"Q2736119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4ade6396fdc1c0f22bb68d1394311b818341385","datavalue":{"value":{"amount":"+0.9120444","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":"Q1124350$B513AF51-57C8-4F12-B9BC-FA3EC9C9FFB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"461d9141354035a34b52c82d900f972033218370","datavalue":{"value":{"entity-type":"item","numeric-id":3032302,"id":"Q3032302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d31724200bf1adb8ef481838bd5c2bf05f573ef","datavalue":{"value":{"amount":"+0.8981216","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":"Q1124350$514665AC-056A-4BF2-935D-4DCCF61EF27F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"040ec92cc214599ecdf38d6bd02ff3927f501733","datavalue":{"value":{"entity-type":"item","numeric-id":1669583,"id":"Q1669583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6af5b0788838f59b8c0574aac41a1eccc9930d5a","datavalue":{"value":{"amount":"+0.8945611","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":"Q1124350$255A1DAD-C802-4E99-9054-CFF92973F6D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46944bb8da42e8da4a7af99ea3d9b322c9f22d85","datavalue":{"value":{"entity-type":"item","numeric-id":4037299,"id":"Q4037299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3ce6a6508d9c08f81df5d3d08e6e9fb206d66f5","datavalue":{"value":{"amount":"+0.88904184","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":"Q1124350$397342DE-FFE5-463A-A8E1-7222A4F6053A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36c07be3a81a593d5fd87aaa23a4edcc6c764e2c","datavalue":{"value":{"entity-type":"item","numeric-id":4285634,"id":"Q4285634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3ce6a6508d9c08f81df5d3d08e6e9fb206d66f5","datavalue":{"value":{"amount":"+0.88904184","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":"Q1124350$58E8E81D-23D7-44B4-B4AB-DEEF46DDA8D5","rank":"normal"},{"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":"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":"Q1124350$492273B7-A7F8-4B64-ABFE-B76489396DC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a5977731195cb8d9dab31386e35ee7e96b93657","datavalue":{"value":{"entity-type":"item","numeric-id":1110330,"id":"Q1110330"},"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":"Q1124350$2B465A22-30BA-48F2-ADC6-CE7EF7277AD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8cd0ea8c677ccb5e707eba3ce592df495f7e48a","datavalue":{"value":{"entity-type":"item","numeric-id":1657766,"id":"Q1657766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d898339f7dc7f4c6aa283d4f27e9d201fb365d29","datavalue":{"value":{"amount":"+0.8791708","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":"Q1124350$86B0A515-7A0A-4773-8E39-CD495F4F8040","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65fe5830e0db07645cadfabd6ac894eb0fd8e9be","datavalue":{"value":{"entity-type":"item","numeric-id":3979384,"id":"Q3979384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a39a3da581efc4960eb45e40806ea2f96689ec5","datavalue":{"value":{"amount":"+0.8729126","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":"Q1124350$F4AFDBE5-7E1F-4261-951F-7EE99F883E5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"044c630c3a1392dd9874cac0f98eaf8c75cf65cf","datavalue":{"value":{"entity-type":"item","numeric-id":1854433,"id":"Q1854433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de72c3b9082603cc24dcec4a80d5f456c14e2e12","datavalue":{"value":{"amount":"+0.8720337","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":"Q1124350$E0CD0CD1-A986-4463-9094-31DB234F1EF8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1124350","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1124350"}}}}}