{"entities":{"Q2236804":{"pageid":2247547,"ns":120,"title":"Item:Q2236804","lastrevid":57803877,"modified":"2026-04-02T14:41:50Z","type":"item","id":"Q2236804","labels":{"en":{"language":"en","value":"Edge-disjoint branchings in temporal digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7414022"}},"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":"Q2236804$DA4CEE48-8CB1-44F6-A8A0-D257B423A9EB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5f8679998df2e57e351e011256f4b46ab423b14","datavalue":{"value":{"text":"Edge-disjoint branchings in temporal digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2236804$58AD1ABF-B002-455E-B20B-40EB612A284F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"323b498df84e840b338d336d4c1dbdddcf15df9a","datavalue":{"value":"1476.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2236804$1CE6FE70-81E7-4C2C-B7BD-36F184B21F99","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"07211ea356ff618be37091fa273e3707036d832e","datavalue":{"value":"10.37236/10229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2236804$496E829F-D54B-4038-9427-9D4816C6A14D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$7591F4CC-B116-45D6-B7C5-9053AD882D71","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$E90C3F61-E28E-4CDA-B0B0-034BDA384013","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"60f74372e81e626b6210280e003a15953819ad37","datavalue":{"value":{"time":"+2021-10-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2236804$56DF177F-3CE7-4223-9619-72B1B868F657","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"719ded890989ceba89aceb0b96a3d3ecd1370ebd","datavalue":{"value":"https://arxiv.org/abs/2002.12694","type":"string"},"datatype":"url"},"type":"statement","id":"Q2236804$2D575B6D-32B2-4688-93EC-668BCA1E35D6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b48bdc78e8bd5bd010c6bb71be73e85b613b774b","datavalue":{"value":"Summary: A temporal digraph \\(\\mathcal{G}\\) is a triple \\((G, \\gamma, \\lambda)\\) where \\(G\\) is a digraph, \\(\\gamma\\) is a function on \\(V(G)\\) that tells us the time stamps when a vertex is active, and \\(\\lambda\\) is a function on \\(E(G)\\) that tells for each \\(uv\\in E(G)\\) when \\(u\\) and \\(v\\) are linked. Given a static digraph \\(G\\), and a subset \\(R\\subseteq V(G)\\), a spanning branching with root \\(R\\) is a subdigraph of \\(G\\) that has exactly one path from \\(R\\) to each \\(v\\in V(G)\\). In this paper, we consider the temporal version of Edmonds' classical result about the problem of finding \\(k\\) edge-disjoint spanning branchings respectively rooted in given \\(R_1,\\dots,R_k\\). We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal digraphs. A branching \\(\\mathcal{B}\\) is vertex-spanning if the root is able to reach each vertex \\(v\\) of \\(G\\) at some time where \\(v\\) is active, while it is temporal-spanning if each \\(v\\) can be reached from the root at every time where \\(v\\) is active. On the other hand, two branchings \\(\\mathcal{B}_1\\) and \\(\\mathcal{B}_2\\) are edge-disjoint if they do not use the same edge of \\(G\\), and are temporal-edge-disjoint if they can use the same edge of \\(G\\) but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are NP-complete, even under very strict assumptions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2236804$0CCFF8B4-6FD5-4BA5-B173-2016C60B55F6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2236804$1449DF11-AFF9-47B8-93AE-321EFE77E586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2236804$12FD6A55-CABA-4977-B0CC-0B2B6F4498FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2236804$94152E51-A24E-42B1-ADE7-6A0BEA2DCD5A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5443f715d7a233d875018f847963157a69f5d29","datavalue":{"value":"7414022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2236804$54392AE2-30E1-4604-A02B-6761C59A54F1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1082b4872f68d4c51f4fd8ad9b70c76d1b54d8d","datavalue":{"value":"spanning branching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2236804$5DA3D9C9-A4D4-4BA4-BF48-1E328A5B2713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9948c373763547091d26331b6a190fd84a74f00","datavalue":{"value":"base static digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2236804$5B120A04-FAA7-4AAF-9F2B-1C2F49B371AB","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":"Q2236804$DCBDC6CB-8BBD-427C-B836-86FDF83F1975","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"516714f15ba13b2423b6bf4af181f92dc11e7f17","datavalue":{"value":"W3206407623","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2236804$14BA53F3-3E37-4947-B8B5-AAEEC9080BCA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dc80b40ab2ac769bf40ad17bea02aff7750d565","datavalue":{"value":{"entity-type":"item","numeric-id":5689807,"id":"Q5689807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$F4789ECF-6A6B-459D-9A50-3E408C1425C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29b7ddd90efd852a7ec91d544179ef0a20ae3eb3","datavalue":{"value":{"entity-type":"item","numeric-id":5696908,"id":"Q5696908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$F677E798-D35A-45C2-9FF7-506561AE23B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa1904ea1654cb059b1bc3135abbd68a99d2eaf5","datavalue":{"value":{"entity-type":"item","numeric-id":5041184,"id":"Q5041184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$893B3AA2-6ADB-4DC2-A912-BF472515B31F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08cc9cdd9999a46859ae4f667ab34baac016718b","datavalue":{"value":{"entity-type":"item","numeric-id":5502162,"id":"Q5502162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$F91D4A87-B8EC-4676-9F63-290A4107537A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34df8a11b2c88ad111f7da220b68698668414dbf","datavalue":{"value":{"entity-type":"item","numeric-id":4070624,"id":"Q4070624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$83DE0BCF-0E1D-4031-8BE3-F58C80F11D6B","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":"Q2236804$7C0F3F88-88EA-4FAA-8B55-D15DBA03924D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59c5209ea8dce2620de8c0c7c4e141ffb80451c0","datavalue":{"value":{"entity-type":"item","numeric-id":3858297,"id":"Q3858297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$DA92367D-B455-4DA9-9584-BA9D6CAEE30D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"538db66766db6677e77c4aa4dc33fce284f0e7af","datavalue":{"value":{"entity-type":"item","numeric-id":4113865,"id":"Q4113865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$799A8181-5718-44C9-9C7F-1DB2A0257ED4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d056eb33322871d732919445c966650b417c9665","datavalue":{"value":{"entity-type":"item","numeric-id":5894823,"id":"Q5894823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$CDFB148D-31A4-4905-B6F6-3081DED533C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4a40eec7c3892237ba8733670ebe1f5506614d1","datavalue":{"value":{"entity-type":"item","numeric-id":1229885,"id":"Q1229885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$4C77640B-C81D-40F3-888B-5365982F189D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"838956d6be288d1dc8262556ca9ecc6197b91387","datavalue":{"value":{"entity-type":"item","numeric-id":4740329,"id":"Q4740329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$5666B722-DEAB-4816-ADDA-116573703892","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0da3b995f26b7f7df55fdba84117178d4c80116c","datavalue":{"value":{"entity-type":"item","numeric-id":1739101,"id":"Q1739101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$F9EE51C4-436D-4383-B0E2-481DA8D5CEA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96dfebbe470e9b35cf3770366666741c7ff17fbe","datavalue":{"value":{"entity-type":"item","numeric-id":5856438,"id":"Q5856438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$E280113C-3262-40EB-ADC8-BC92BB2FE419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"070bcdc321023e903814ac9591b55c96fdaa88df","datavalue":{"value":{"entity-type":"item","numeric-id":3090774,"id":"Q3090774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$CB2F6FFF-A171-4A4B-B0C2-ED6A44FF76A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$018DFEC9-D0BC-4D7B-8EA0-2F5C9CBCE746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c01149a6900c0f611a509645affd60c9a396109","datavalue":{"value":{"entity-type":"item","numeric-id":1854113,"id":"Q1854113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$BAE5B12C-ACD1-47C3-8A68-7CA0A2B29705","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1a9149a558712bf3803622c50763403488e2a3c","datavalue":{"value":{"entity-type":"item","numeric-id":1255784,"id":"Q1255784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$288DDE49-DDF9-4415-9247-277056EB4EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f02bd01dbd79b6e1db29c2f7faa4fae519d47e9b","datavalue":{"value":{"entity-type":"item","numeric-id":3084217,"id":"Q3084217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$967C3AEC-FDB4-4D99-B747-019BB87F613B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b938085d20cca1d55ccd08fb0afe80715e3416d0","datavalue":{"value":{"entity-type":"item","numeric-id":1214942,"id":"Q1214942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$7CCD4989-D7EC-4D4D-BB7A-0DA3D2EE2681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5325820f1da9bdbe993d9d54d34a90dc88d69e8e","datavalue":{"value":{"entity-type":"item","numeric-id":4869540,"id":"Q4869540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$419D6F7E-B03D-4B1A-A1ED-263542026208","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b2cafd376cc7060a9820cd4cf07fb62d40047c26","datavalue":{"value":"bafkreiavusumunmikslafavrh25avhthwncvb6e2o7gggefcw6ls3tda6u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2236804$85FE9F94-7D61-485A-AD9A-B8C0C6370036","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a336f6e03576ab1e29bbef91e85855101da79d7","datavalue":{"value":{"entity-type":"item","numeric-id":477677,"id":"Q477677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bd96afa0e1be34c4a7cebf30fd4216970dafe75","datavalue":{"value":{"amount":"+0.7474928498268127","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":"Q2236804$5AACB37D-2A52-4215-9049-A4CBC37B170B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60666f5deb5a66e72daddd202e0f75c98f54709e","datavalue":{"value":{"entity-type":"item","numeric-id":5925630,"id":"Q5925630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b60a9f30bbdc93958961fa133729d048271129c","datavalue":{"value":{"amount":"+0.7330089807510376","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":"Q2236804$186E183D-10BD-4226-867A-485234B837E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2259fa18cc64b02e2c400ed721d74132167405e","datavalue":{"value":{"entity-type":"item","numeric-id":5918410,"id":"Q5918410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a75be543bea403ca2e98dfaa4c6c415c8def51c4","datavalue":{"value":{"amount":"+0.7250316739082336","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":"Q2236804$85FA6644-3A71-401A-BFD8-74FCFC769A70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ad4d999b45dd17adaae9c6781897a03f9d2fe03","datavalue":{"value":{"entity-type":"item","numeric-id":5894823,"id":"Q5894823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"372f95e76bad55ed133510ac8fd5f396e4bf7816","datavalue":{"value":{"amount":"+0.7225438356399536","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":"Q2236804$9603F29B-1B30-4D02-919E-31A9146D649D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"838eac088536122c6fb60a67142be08a60d1ec8c","datavalue":{"value":{"entity-type":"item","numeric-id":2192110,"id":"Q2192110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"372f95e76bad55ed133510ac8fd5f396e4bf7816","datavalue":{"value":{"amount":"+0.7225438356399536","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":"Q2236804$1B3A9F90-25AD-4B81-A357-E918053DCD7D","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2236804$D0B18353-B2EE-40F4-9722-5822F1CE1569","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2236804","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2236804"}}}}}