{"entities":{"Q987553":{"pageid":989401,"ns":120,"title":"Item:Q987553","lastrevid":65920482,"modified":"2026-04-12T06:16:30Z","type":"item","id":"Q987553","labels":{"en":{"language":"en","value":"Arc-disjoint in-trees in directed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5770358"}},"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":"Q987553$B11F456F-C377-4D9E-B1BD-F769ED45CF7C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"655e21b5f79ff92dc3cc23d1de107b4f55460e40","datavalue":{"value":{"text":"Arc-disjoint in-trees in directed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q987553$48915CD6-4AD4-4722-97C0-CE866DC088DC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2673695d9a343ef49fbbe040e9121e3e7b3503ed","datavalue":{"value":"1212.05209","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987553$5C1E8473-5E26-4F54-A364-7FFBD64EA7A7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"480f65f1587fa75d2fb9e744db3f9ddcafbeb8ea","datavalue":{"value":{"entity-type":"item","numeric-id":300211,"id":"Q300211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q987553$D8CA870E-75B9-42BA-9978-8A1C2380788F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"857bf70e7d30bebc99244cb54d69e95a358f4fc1","datavalue":{"value":{"entity-type":"item","numeric-id":202561,"id":"Q202561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q987553$34B5F917-9AB1-437A-9399-E5FE5E179DAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"edfb715cc646de13a681799145a206b8405551a7","datavalue":{"value":{"entity-type":"item","numeric-id":967436,"id":"Q967436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q987553$831C8620-61F2-41B6-8738-9C93D37FE87F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q987553$A858237E-8D48-4D54-89FB-DE4981521D18","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"829d55f1ec544e7d684ffd95ef09a9fd350e7c82","datavalue":{"value":{"time":"+2010-08-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q987553$1BB0285B-0F17-4B00-9A01-DCEACA98FD03","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6f514b8cd1441719fe84ef43cc484e2e3a8c8615","datavalue":{"value":"http://hdl.handle.net/2433/123379","type":"string"},"datatype":"url"},"type":"statement","id":"Q987553$B86B1F86-88AB-445E-AC2D-EE4CC061CCFB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"54936107f342813bd55cdbc6b87151cc46278160","datavalue":{"value":"The authors generalize an old theorem of \\textit{J. Edmonds} [Combinatorial algorithms. R. Rustin eds. Courant computer science symposium 9: January 24--25, 1972 (1972; Zbl 0366.68023); pp. 91--96], and a result from \\textit{A. Schrijver} [Algorithms and Combinatorics 24, Berlin, Springer (2003; Zbl 1041.90001)]. The first states that given a directed graph \\(D=(V, A)\\), with a specified vertex \\(s \\in V\\), there exist \\(k\\) arc-disjoint in-trees rooted at \\(s\\) each of which spans \\(V\\) if and only if there are \\(k\\) arc-disjoint directed paths from any \\(v \\in V \\setminus s\\) and \\(s\\). In the other a vertex set \\(S=\\{s_1, \\dots, s_d \\}\\) is specified together with a function \\(f: S \\rightarrow N\\). A more or less straightforward generalization gives a necessary and sufficient condition for the existence of arc-disjoint in-trees \\(T_{i, 1}, \\dots, T_{i, f(s_i)}\\), where \\(T_{i, j}\\) is rooted at \\(s_i\\), and each \\(T_{i, j}\\) spans \\(V\\).  The main theorem of this paper generalizes this statement even more to the case where a \\(T_{i, j}\\) spans only a set \\(V_i\\), namely the set from which the vertex \\(s_i\\) is reachable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q987553$F242A2EB-70CB-42EC-85E2-EDA1F6FF5A0C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q987553$AA7B19A6-E68E-420C-A799-823F9E4973B9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987553$A07EB21B-40C7-4AFD-8625-B7D0032EB03D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987553$48BD6762-374E-4C32-B02B-A921F0879CC3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b69ceb5585d31822b3ed7d123e0b1691c3e5b0f2","datavalue":{"value":"5770358","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987553$5970068F-1A80-4A96-B175-DC549D3A53DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d7fa12204e92e17ac5d0834ec9644bd446105e5","datavalue":{"value":"arc-connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q987553$93121DB7-F4F6-43FF-A3EB-EB9508DA6D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"adbbee23ed0de6af7662cbdc1213772da6d28bbd","datavalue":{"value":"directed trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q987553$9836A80F-9CC6-4C53-AA8C-1B61718C8A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"093ef3cbea03ec661dc66ae3009ad13581b7249b","datavalue":{"value":"packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q987553$6E818433-23B2-4F1E-A0D6-B39B7F900F60","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":"Q987553$0B7FA05C-A41A-43D0-A393-01891CB6111A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"24b13fdf70d6194a7c009e827ea04739f84bee73","datavalue":{"value":"W1987229183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987553$4884167C-9109-424A-B040-B03046ADAF8B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"1176036cf46221da5335bd5770d216daf41bda57","datavalue":{"value":"Q126592761","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987553$252ED499-16CE-4B96-B50B-6D55059D38BC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"347b400a80d973716dc8247163e9ae75f1685ccc","datavalue":{"value":"10.1007/S00493-009-2428-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q987553$FE463A5C-9CC5-4D9B-935D-D8796E085FBD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f94fa423856f06eb6bab2d424ae57c173c66ac14","datavalue":{"value":{"entity-type":"item","numeric-id":1773369,"id":"Q1773369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00694515e1be5bf65574e1a9c0f159b1782376ed","datavalue":{"value":{"amount":"+0.8416017293930054","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":"Q987553$151375CA-87EE-406C-958F-96555EFA5F6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1592b03a63b70695366849d6674b00405c120be5","datavalue":{"value":{"entity-type":"item","numeric-id":3826584,"id":"Q3826584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"883ebe56325bb7958908370d3187241f7571976f","datavalue":{"value":{"amount":"+0.8236299753189087","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":"Q987553$7EF8C307-85AD-448A-8E36-02292F820794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d07b03acefd14bebb295495b206f5a2a5a13ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1937557,"id":"Q1937557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"663196d110a249601fa0e2ac08b5052d1ffa6de8","datavalue":{"value":{"amount":"+0.8214351534843445","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":"Q987553$6E4C3924-7D0A-4D3A-8B71-830AB4DCCAE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d12279bf8b9423be617255e0a318f9b452e9170","datavalue":{"value":{"entity-type":"item","numeric-id":3511356,"id":"Q3511356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f860002a6fb6c6a0e968a604f5e1ff708e830886","datavalue":{"value":{"amount":"+0.81343013048172","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":"Q987553$8D54D62B-7560-43AC-BD66-91488530BB35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dad88ea2f7ab707c2bfba0ce744f539b8a47a1b0","datavalue":{"value":{"entity-type":"item","numeric-id":626455,"id":"Q626455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f85ebb3b5119edaa19df25ca4a8e30c7b2b480f","datavalue":{"value":{"amount":"+0.8069078922271729","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":"Q987553$DA98FBEA-B81C-4520-B46D-241F81CEC619","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Arc-disjoint in-trees in directed graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Arc-disjoint_in-trees_in_directed_graphs"}}}}}