{"entities":{"Q1908272":{"pageid":1919014,"ns":120,"title":"Item:Q1908272","lastrevid":47396644,"modified":"2026-01-01T15:14:49Z","type":"item","id":"Q1908272","labels":{"en":{"language":"en","value":"Packing Steiner trees: Further facets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 847629"}},"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":"Q1908272$40087622-7575-4603-88DA-2E90C32E2C49","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bb6ee070dbca11dbe2b39bc9db8da4dacab16fd5","datavalue":{"value":{"text":"Packing Steiner trees: Further facets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1908272$B036048E-64DF-4044-9E5B-E1CC6CAA7BBD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2dfdbf54daec0fb85ab5691179e4e31b91b9fe60","datavalue":{"value":"0841.05078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1908272$12B3884A-BA27-40DA-ABCC-315215EB25A5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc559bb8ef1f25204ce5a4ae8402ff1f1894883c","datavalue":{"value":{"entity-type":"item","numeric-id":323369,"id":"Q323369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1908272$407AD779-6747-48A4-B8A8-AB545D21DECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c79d63a974620aa9dd22e3cdec2e56a2714b61d9","datavalue":{"value":{"entity-type":"item","numeric-id":202055,"id":"Q202055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1908272$F7DEFD35-54F9-4D5D-B8B3-DD8B9B5C3C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc0bd20b49fc5f8c46a35ef243535d5a3fb2bd74","datavalue":{"value":{"entity-type":"item","numeric-id":210498,"id":"Q210498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1908272$95C6BCE3-CD04-46D8-97F9-C98D6A58ED8D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1908272$09232F42-E34D-438E-8F83-DE16A89307F5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1ca13147794ee6248df993be52ba350f706942fc","datavalue":{"value":{"time":"+1996-07-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1908272$0C2D4E54-6B7F-440A-AA5D-570F6A98453B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d3634b3697c64cd2817bf31a14bacb55193b579","datavalue":{"value":"https://semanticscholar.org/paper/d9d4143501a2349fa3c64a8daaec25660ee169e4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1908272$4DAE0E49-38ED-4A2B-92FF-3D8F08F7FA63","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3889fbb40c197675216dfbc17f268148db23d0ce","datavalue":{"value":"Let \\(G= (V, E)\\) be a graph with positive integer capacities \\(c_e\\) for all \\(e\\in E\\). For a subset \\(T\\) of \\(V\\), an edge set \\(S\\) of \\(E\\) is called a Steiner tree of \\(T\\) if for each pair of nodes \\(u, v\\in T\\), \\(S\\) contains a path between \\(u\\) and \\(v\\). Let \\(T_1,T_2,\\dots, T_n\\) be node subsets of \\(G\\). The Steiner tree packing problem is to find Steiner trees \\(S_k\\) of \\(T_k\\) for \\(k= 1,2,\\dots, n\\), such that each edge \\(e\\in E\\) is contained in at most \\(c_e S_i\\). This paper investigates the Steiner tree packing polyhedron, establishes several new classes of valid inequalities and gives sufficient (and necessary) conditions for these inequalities to be facet-defining. These inequalities can be used to be incorporated into an existing cutting plane algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1908272$7D2501F9-C20D-4B5E-B32D-98A7E970FF5A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1908272$6DE72E56-FD13-4C90-ACAF-65F37441F065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1908272$A4D9AB61-395F-4930-AD29-9EC957EC4A6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1908272$6EA01EB3-F5C2-455C-BB33-6794FC21C5A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1908272$10475BFD-AEEA-40D3-8D7D-DAFDCD536872","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"69e166eebf679711c3e2d933279a7897574152de","datavalue":{"value":"847629","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1908272$1C5B99CD-CC8B-470B-A73E-70D4C012D97B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"66a0382610d9d9e28ef95c946357abf690b72349","datavalue":{"value":"Steiner tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1908272$C3611AEF-FB12-42B5-B062-9B51B75A64FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1908272$44327FB0-2882-4884-A921-AE8B005FB44C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"83063f903568a97e01ab807d046e33369447d159","datavalue":{"value":"Steiner tree packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1908272$7CB6BF75-3738-40A0-9F25-ADEDF47BC988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88e97179649b5d7f96289ce6712e2ee9e33456ce","datavalue":{"value":"Steiner tree packing polyhedron","type":"string"},"datatype":"string"},"type":"statement","id":"Q1908272$D1D719BA-B91D-4862-A90E-DE7BF98BA99A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5bbd8c55216bc58296fa2ade785c5de51a5a6c4","datavalue":{"value":"cutting plane algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1908272$96FC45BB-A721-4892-B001-68F6D5A17B02","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"07239940f627bb41653311a5b39a7820a8be90f7","datavalue":{"value":{"entity-type":"item","numeric-id":199348,"id":"Q199348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1908272$1E411ED3-D9F1-4D65-838E-D89B2C6E7BF8","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":"Q1908272$0BD805F1-5B3E-455C-B684-770B23BC103B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"39416fe1f22f37989689d69ba49575eb1a04b99c","datavalue":{"value":"W2080978495","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1908272$F1E204EE-A707-4997-909E-E3325E722026","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"953560ef9c144c97db1035f27d3fc8ab60a11ef0","datavalue":{"value":"10.1006/EUJC.1996.0004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1908272$985C6332-7105-48EA-BF34-A561E6611F58","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1b9836576a7e1ea05473f0b88538d4720b09945","datavalue":{"value":{"entity-type":"item","numeric-id":1919089,"id":"Q1919089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e43f75210899b9ea1b8ad4b0eb5f616d6ec268b1","datavalue":{"value":{"amount":"+0.9269824624061584","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":"Q1908272$0284FF8B-E755-4162-877A-06553E2E6E91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22b5940439056a729d45a317a29d632b8b934065","datavalue":{"value":{"entity-type":"item","numeric-id":1322552,"id":"Q1322552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e43f75210899b9ea1b8ad4b0eb5f616d6ec268b1","datavalue":{"value":{"amount":"+0.9269824624061584","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":"Q1908272$3D54EB11-F5E7-49D1-A277-4032BD664AFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"970c66e22a1227d910fe1120b9effa3bf1a6687c","datavalue":{"value":{"entity-type":"item","numeric-id":5946818,"id":"Q5946818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad1abf7dce2de47ccce8e3a3754644d4dcb0b59b","datavalue":{"value":{"amount":"+0.8416697382926941","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":"Q1908272$225F5DB5-7BD2-4EC5-8845-D2D6EE58796F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2fc2f65391730aaf84a6539eb6216d819b730f3","datavalue":{"value":{"entity-type":"item","numeric-id":3484640,"id":"Q3484640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad1abf7dce2de47ccce8e3a3754644d4dcb0b59b","datavalue":{"value":{"amount":"+0.8416697382926941","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":"Q1908272$01DBD572-D080-4916-A703-E5771768EE32","rank":"normal"},{"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":"e9ef51b0da5cc1429110929f8ac4e2a639f0bb33","datavalue":{"value":{"amount":"+0.8363140821456909","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":"Q1908272$9D722A1F-553F-4A2F-AF7A-A72B8090F0A2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1908272","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1908272"}}}}}