{"entities":{"Q925137":{"pageid":926985,"ns":120,"title":"Item:Q925137","lastrevid":50368976,"modified":"2026-01-13T22:03:34Z","type":"item","id":"Q925137","labels":{"en":{"language":"en","value":"An approximate max-Steiner-tree-packing min-Steiner-cut theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5281487"}},"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":"Q925137$C63E08CD-496F-4C6F-A76E-97429282BDA4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2e7822c588bfbd4358fd53cf1134643d888a7f0d","datavalue":{"value":{"text":"An approximate max-Steiner-tree-packing min-Steiner-cut theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q925137$1855D4B0-2A1F-483D-8A15-EDE70EA4EEEF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a54e03947698b73d2893bb96b848167efa797b4f","datavalue":{"value":"1136.05011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925137$1FC14E70-60A9-46A6-BB26-8682C0833D7E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"29b87779f5a562ce1ba99b084acea89bd5e59b91","datavalue":{"value":{"entity-type":"item","numeric-id":925136,"id":"Q925136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925137$8A3B3A8D-7AE2-4E0A-A76B-C11D40D4C70A","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":"Q925137$DB4851E8-7105-4A0D-810E-4EE95DFAE10D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6d5ea9744be37dbc33ed76d7f80e76e9dbefcded","datavalue":{"value":{"time":"+2008-05-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q925137$E620ECDC-EBB2-460A-AED0-9E907DFE06B3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1fd93ffa93dcd82afe9c44d901a34ae788096462","datavalue":{"value":"Given an undirected multigraph \\(G\\) and a subset of vertices \\(S\\leq V(G)\\), the Steiner tree packing problem is to find a largest collection of edge-disjoint tree that each connect \\(S\\). \\(S\\)-cut is a subset of edges whose removal disconnects some vertices in \\(S\\). We say a graph is \\((k-S)\\)-connected if every \\(S\\)-cut has at least \\(k\\)-edges.   Author proves that if \\(G\\) is \\((2k-S)\\)-connected, then \\(G\\) has \\(k\\)-edge-disjoint trees. The proof is constructive, so if \\(G\\) is \\((26k-S)\\)-connected, then a collection of \\(k\\)-edge-disjoint \\(S\\)-tree can be constructed in polynomial time. It is a first polynomial time constant factor approximation algorithm for the Steiner tree packing problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q925137$FD4BC70F-0ECC-495B-AA53-3EE982386F2D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"537fadaa81863f07c95f9ce70feadc229f68c3c5","datavalue":{"value":{"entity-type":"item","numeric-id":860608,"id":"Q860608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925137$6189F26B-2F4C-4179-B828-F8E5E9CC0A9F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925137$E74A5F15-4654-4D11-BCB2-ACADE0BCA439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925137$A52EA422-A683-49F6-8FAD-C1928FA8CF77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925137$96308066-57C9-4ABB-B88A-D19C29BBE3CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925137$AB60CAC4-9741-43CF-A13E-FE07D8894512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925137$DA9E8110-10B4-4ED1-9975-A5CC8D034C81","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"344379ec9d2695cfa68b773aeb56a0c804e9ebeb","datavalue":{"value":"5281487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925137$0E573167-53EE-414A-A4CD-4907F463FA9E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4311c8d22358f4beebba86cb0501951f5abdded2","datavalue":{"value":"approximation algorithm trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q925137$CD7BB1F8-FA40-476B-9275-D037E73446DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ef981f34078b91102475c7a715b82003559b6bb","datavalue":{"value":"Steiner tree packing problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q925137$EF981074-DA76-4805-A377-219ED2D31EEB","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":"Q925137$16A69776-1293-433D-9136-CCCF42A690CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0df1405dd181e9c8175e60917c140a7b35fffb14","datavalue":{"value":"https://doi.org/10.1007/s00493-007-0044-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q925137$C180A00E-4DAF-4661-B4D1-DACBD57BEFA2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0947dd3234e96bcd616e9229c35144d94d17837a","datavalue":{"value":"W2097945626","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925137$63DF0233-3A24-4287-B6C7-B773BF0B31C6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a7064ee01c910fb32772b27dbbe50165f8ba76aa","datavalue":{"value":"10.1007/S00493-007-0044-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925137$1DFBA64E-3F94-45C8-B640-0629B7C18E79","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca6b15cc6edc0e5e05ac666221a815a37f44fdb2","datavalue":{"value":{"entity-type":"item","numeric-id":4471308,"id":"Q4471308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57335e39b7cdb8cf1eda1f4d14d0da628144cd1e","datavalue":{"value":{"amount":"+0.8646880388259888","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":"Q925137$EB89655E-E041-4758-A05D-136E7FB4894E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"463936357af732d609cea3d73dc600769d49fa3a","datavalue":{"value":{"entity-type":"item","numeric-id":3596337,"id":"Q3596337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd1090f9dcfb094d453f8a711d1daefba9280761","datavalue":{"value":{"amount":"+0.8635271787643433","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":"Q925137$68E9A8F3-636F-4EA4-8EF6-3F584F01CA6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a81749d9f6c138711175c200f7a2e3d2936c8a4","datavalue":{"value":{"entity-type":"item","numeric-id":273179,"id":"Q273179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"404bc519752034181f26c4da8c7428f7d6aa1dc3","datavalue":{"value":{"amount":"+0.8289414048194885","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":"Q925137$D0DDB261-6141-4CDD-8F32-CBBBC65F262D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"688313d01e3cc812b7eb635b9c78927746ce44e0","datavalue":{"value":{"entity-type":"item","numeric-id":3057108,"id":"Q3057108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44e7c01b9438d4e890485fb00b28d6830c9fe694","datavalue":{"value":{"amount":"+0.8277372717857361","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":"Q925137$8D75FABC-2198-408C-B396-9768827915B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92616a8058c76c4ed8cdfe26267523a887f34245","datavalue":{"value":{"entity-type":"item","numeric-id":5464577,"id":"Q5464577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1038d109b2bff0869299feaec047cc6f7a2bf10","datavalue":{"value":{"amount":"+0.8226656317710876","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":"Q925137$026DD778-505D-45E6-A2F5-D160B8AD0D0C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:925137","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:925137"}}}}}