{"entities":{"Q1057282":{"pageid":1059130,"ns":120,"title":"Item:Q1057282","lastrevid":48800590,"modified":"2026-01-05T21:40:52Z","type":"item","id":"Q1057282","labels":{"en":{"language":"en","value":"The 2-linkage problem for acyclic digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3896961"}},"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":"Q1057282$68AD2EC9-365B-450A-888B-7AB2F3CF0D79","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f26c981c03cc532267557703bc6a4cecacedb4e6","datavalue":{"value":{"text":"The 2-linkage problem for acyclic digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1057282$E3338851-80CA-451A-9F2D-ADF1B78C6024","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eafdcd97d1746b56e45d6c39134a1a56585135c4","datavalue":{"value":"0563.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057282$9C60E4C1-C888-481F-8852-964F2811A0B5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"37a0eb30e12050ddf0064bbafccf6e7f201e1e20","datavalue":{"value":"10.1016/S0012-365X(85)80022-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057282$7685D8C8-6D55-4C43-9506-F7A888408FBB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aec857263cee52fe850f36c12f5157e5c8f0a013","datavalue":{"value":{"entity-type":"item","numeric-id":228790,"id":"Q228790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$434D046D-7744-45DE-9941-3B023CA4D2F5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$8E0A34DD-0C76-4C92-8D15-E3FBEE674364","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1057282$EC64F680-C66A-4B07-97E4-EFD835E99B45","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dd283dedf60b78656ca990dff05437a09d61a7a6","datavalue":{"value":"The paper solves the problem of finding two disjoint directed paths with prescribed ends in an acyclic digraph. This is accomplished by reducing the problem to one of planarity test of an undirected graph. Necessary and sufficient conditions are given in terms of certain forbidden subdigraphs. As a result, it is shown that if any three cycles of a digraph have a common vertex, then all cycles have a common vertex. A precise structural characterization of digraphs of order n and girth \\(g\\geq 2n/3\\) is given. From this it is shown that any such digraph has at most \\(3^{n-g}\\) distinct cycles and that a digraph of order n and girth \\(g\\geq 4\\) has at most \\(2^{n-g}\\) shortest cycles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057282$E2817741-C0B4-484A-BF5F-3C19A9390E96","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99fea3d876487c7181e0dff689e3c55a44323330","datavalue":{"value":{"entity-type":"item","numeric-id":592071,"id":"Q592071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$8860BB35-BF64-42B2-B789-03A8768517FA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057282$A0B76ECE-2F4E-42C6-BA19-6F0F6882195C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057282$82C97921-084A-48B0-AE9D-69E7EEA88FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057282$C6CE3F28-A244-4A66-A3EA-BEBB4DF353B8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"44f42bcfe3e2fe2660401a96801ee993626b1c8f","datavalue":{"value":"3896961","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057282$80CCDF7D-0BED-49F9-8416-4DAE39814007","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddd295793a7ba9cea406dcb50d744aa898eea678","datavalue":{"value":"directed paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057282$412E9DCC-1876-4AAB-A182-7DBFC07441C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"298a551ef47c5b20057a4bfdb8bbc9e28d84ca03","datavalue":{"value":"acyclic digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057282$6AFCF2C2-202C-49DF-B817-A0E6D4BEDE13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b809c1237ed45910b34f5fc615f6bcd92be992","datavalue":{"value":"distinct cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057282$A89C12B7-2A41-43A7-ABC9-6FAFF1FC6462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6397697b54a06a190e17f726d2ae8d3e7a8f6c4","datavalue":{"value":"shortest cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057282$CAC9C1F5-FB0A-4224-9C59-95477529046E","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":"Q1057282$0D2D8071-ADC9-4B4B-BB30-E11449D39FB2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"80cd2af8cbfd9c839139d3938418c7fc3dc07538","datavalue":{"value":{"entity-type":"item","numeric-id":1058526,"id":"Q1058526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$E4A6A648-8903-46BA-9D5F-32312BA14003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b3d018f710168a4c0bbc22dd78d95193c542bca","datavalue":{"value":{"entity-type":"item","numeric-id":3907591,"id":"Q3907591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$A1D36334-75A6-45D0-9061-D1F2109BF6BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdc57cf2ba5617fc074cae34fef64910590e17f4","datavalue":{"value":{"entity-type":"item","numeric-id":5331549,"id":"Q5331549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$CE0E73A1-5F3D-4251-A65E-0931D4148DDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b82631da6917417897f9de979a35be56476ede5","datavalue":{"value":{"entity-type":"item","numeric-id":4192089,"id":"Q4192089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$D4FA6FCF-37B7-4436-B282-E20075F6AFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2045a7ec56e01f15e3eae4db248ef2b73a81db","datavalue":{"value":{"entity-type":"item","numeric-id":1132111,"id":"Q1132111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$622F0EAC-A4DF-440F-86B6-3DCE35E27DB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$F41F3091-29DA-4C6D-A88F-0605E2D2DD45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ec6f9887f2638cbba62b2939236956ee0c81ad","datavalue":{"value":{"entity-type":"item","numeric-id":4163550,"id":"Q4163550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$447C8F2C-2C72-4458-A416-DC8AD3C00F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d835ccc7da104c96eb1a22d7d8e47a280dbf09","datavalue":{"value":{"entity-type":"item","numeric-id":1150632,"id":"Q1150632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$A42D739F-D5B4-4624-8338-2C6E670AC58C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"463f0cac3e60d82d492cd248d7fbeefa8310d26f","datavalue":{"value":{"entity-type":"item","numeric-id":1150633,"id":"Q1150633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$F2633532-B4E4-486D-8EE1-F2A3F9B291A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f41d49e608d5ffc8abc77bd4e4e561119c3c473e","datavalue":{"value":{"entity-type":"item","numeric-id":1142781,"id":"Q1142781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$176E2DBB-3E76-49F6-A312-AB4329C25CD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"354a350a19b7f023b6db0fa371461b95e5edb9c6","datavalue":{"value":{"entity-type":"item","numeric-id":595675,"id":"Q595675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$11D3028F-7C9A-4A4C-BF9D-29723F66F0F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94e869ca371191d162cf54235fb110613ed90496","datavalue":{"value":{"entity-type":"item","numeric-id":4177599,"id":"Q4177599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057282$9A8A89A0-B7A8-4F01-B790-720EB650D4CF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cef3d9ca6848b18b4da38117b71dd0b5d5bf91c4","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(85)80022-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1057282$C72AE4C9-0C7C-4791-8E31-6FD430C5AEA1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e5a08830cd969d65b0c0828628a6e04ce8d2354d","datavalue":{"value":"W2025391779","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057282$67B88796-C6B4-41C3-94E8-89A9FBFCED72","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2930a1d56f65de4e6ff2cae66f87fbc6a1da6d65","datavalue":{"value":{"entity-type":"item","numeric-id":3815328,"id":"Q3815328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98edca0fb6266e5981c812b9b93d1a24deec95a5","datavalue":{"value":{"amount":"+0.8330085873603821","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":"Q1057282$A2CDDEAF-304A-4FC9-89CF-5F822813353C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffe6fbffafff9b45ff27ef207d30e4a09e94ad4e","datavalue":{"value":{"entity-type":"item","numeric-id":1092919,"id":"Q1092919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c0b72d5efaa289a6bec7cf25a5b81b6168a0ae5","datavalue":{"value":{"amount":"+0.8140721321105957","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":"Q1057282$7ACF9C6A-65B6-4BFB-ABF0-5A8396993202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af8ca4b098e3e7c8d60de4c8d65d6a05f399ba28","datavalue":{"value":{"entity-type":"item","numeric-id":1325242,"id":"Q1325242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cf760c4ebe408dc6af3db86b9ffafd2e306cc19","datavalue":{"value":{"amount":"+0.801616907119751","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":"Q1057282$6580EB57-D608-4B8D-9A1C-843AE41B8782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e559f0d1e846650b94107ebd4746f6b03768e49e","datavalue":{"value":{"entity-type":"item","numeric-id":2428634,"id":"Q2428634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecd3c18e84ad7960970659696b660c8ce7997daa","datavalue":{"value":{"amount":"+0.7983742952346802","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":"Q1057282$A10BC742-14A2-4FA1-8056-A9BBB096810A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7764f7fed97d58d0adfadd52cc6679b8ee66a919","datavalue":{"value":{"entity-type":"item","numeric-id":2304550,"id":"Q2304550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d00611c521eaea097bc28c26d7e631b4ad7277d9","datavalue":{"value":{"amount":"+0.7937801480293274","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":"Q1057282$81C2DCF7-92A6-4C66-A979-012A5D590A3E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1057282","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1057282"}}}}}