{"entities":{"Q1322552":{"pageid":1333302,"ns":120,"title":"Item:Q1322552","lastrevid":67538031,"modified":"2026-04-12T18:40:39Z","type":"item","id":"Q1322552","labels":{"en":{"language":"en","value":"The Steiner tree polytope and related polyhedra"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 563258"}},"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":"Q1322552$07A6AB08-A2B9-4DBD-A202-16F4DE53C105","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"80f649db6c0e5d344b19b897327891cfeb3e7273","datavalue":{"value":{"text":"The Steiner tree polytope and related polyhedra","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322552$EB732848-B75C-4506-84B6-93B1680979A9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8bf026d8ec5edc206bf7fa3b2193a7a8808974d6","datavalue":{"value":"0808.90124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322552$3DCEE158-E299-497E-B750-BE5911E9EBDF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"664f64d4c6286e547a6497847bdb35c20130fd98","datavalue":{"value":"10.1007/BF01582064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322552$C2A77D04-BBD7-4CAC-8620-04DACDE98E63","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb42abb4d03c24c0e42c27e662a950bd082fe46","datavalue":{"value":{"entity-type":"item","numeric-id":687041,"id":"Q687041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$452D45BA-8585-4FCD-AB4F-B028300CD9B1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$1CF123B0-331C-4F81-A533-B6487FE36AB9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae4d7b05535bc7692a75fc587d4810a7bdebded5","datavalue":{"value":{"time":"+1994-05-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1322552$32F013EC-0070-4731-B8E3-6250DEC6E6B8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ed416dc96df4772f02ff78c90a085ca31a303a59","datavalue":{"value":"The author considers the vertex weighted Steiner tree problem, an extension of the classical Steiner tree problem, from a polyhedral point of view. Given an undirected graph \\(G= (V,E)\\), a set \\(T\\subseteq V\\), a cost function \\(c\\) defined on \\(E\\) and a cost function \\(f\\) on \\(V\\), the requirement is to find a Steiner tree \\((U,F)\\) minimizing the total cost \\(c(F)+ f(U)\\). This problem can be seen to be a special case of the \\(r\\)- tree problem. Here, the requirement is to find a tree \\((U,F)\\) rooted at a given vertex \\(r\\), minimizing again the total cost \\(c(F)+ f(U)\\). The author gives formulations of both problems as integer linear programs. To every \\(r\\)-tree or Steiner tree \\((U,F)\\) he associates an incidence vector \\((x,y)\\) defined by \\(x_ e= 1\\) if \\(e\\in F\\) and 0 otherwise, and \\(y_ i= 1\\) if \\(i\\in U\\) and 0 otherwise. Denote by \\(S_{rT}\\subseteq \\{0,1\\}^{| E|+ | V|}\\) the set of incidence vectors of \\(r\\)-trees and by \\(P_{rT}\\) the polytope of vectors feasible for the linear programming relaxation. Similarly, \\(S_ g\\) and \\(P_ E\\) stand for the corresponding sets of vectors in the relaxation for the vertex weighted Steiner tree problem. In the first part of the paper, the author presents necessary and sufficient conditions for the inequalities in the relaxation of his integer program formulation to define facets of \\(\\text{conv}(S_{rT})\\). The next section deals with the polyhedral characterization of \\(\\text{conv}(S_{rT})\\) for series-parallel graphs. The main theorem proved is that in this case \\(P_{rT}\\) equals \\(\\text{conv}(S_{rT})\\). Thus, one obtains a complete description of the polytope by linear inequalities, when the underlying graph is series- parallel. The last part of the paper considers the projection \\(P_{ST}\\) of \\(P_ E\\) onto the \\(x\\) variables for the case of a general graph. The author proves a number of necessary conditions for large classes of inequalities to be facet-defining.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322552$36BCB357-F19C-4CB1-BD73-6FBEA9B83470","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322552$D8A99F65-87C6-4FFC-A518-336FCA5E6F8D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6de703fcd1064b94d6401fd7c797c5056b229771","datavalue":{"value":"563258","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322552$0C2CD24B-BC08-4659-8055-5DA3E5D3C06E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ade2294b9d16385f491778b8cd5d0f3acab83d7","datavalue":{"value":"polyhedral characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322552$71BDA7EB-540A-454A-AFB5-0F9E182202D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1617e3aa19d65cbfc80989811e170f60dc5878b0","datavalue":{"value":"projection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322552$1DF67793-2D72-4ED6-800F-11DB7730E33C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"747d0307b6dafcec6e50ba81d3396bbf3812302c","datavalue":{"value":"facets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322552$F4B4FBFF-F762-41AE-AE35-4082209098DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2ebea212b64a4fa705ce4e2bf3c5b7530d753d8","datavalue":{"value":"formulations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322552$B5A83EEC-80E1-4213-ACB4-EA140A5E063B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1a698cee79c954f9f3431c98bcb1ab55d056ab9","datavalue":{"value":"vertex weighted Steiner tree problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322552$9BBA1615-BFE6-4A32-868E-9456B4AE0D1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d79f3a79c9dfbf93d9569057f01d7fe6a24c364f","datavalue":{"value":"series-parallel graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322552$67EE0776-6DE2-4B95-87AA-CA372F8CE676","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"111aa4d205b7adb5a8dca99e52744f61a537d2b5","datavalue":{"value":{"entity-type":"item","numeric-id":647398,"id":"Q647398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$504160FF-51F2-4356-87E3-B03172DD9557","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":"Q1322552$60B5FE92-1370-4961-91EF-633E1821CEB6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"884df33512ab676d3bd026b41aede33c2a51bd0c","datavalue":{"value":{"entity-type":"item","numeric-id":3996173,"id":"Q3996173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$78BEF22F-2583-4361-A35D-195054CBB046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$C61927B8-D949-4457-81ED-247067B719E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc69c6156e9471fec17a5d754a7b363dbf0153f6","datavalue":{"value":{"entity-type":"item","numeric-id":3812222,"id":"Q3812222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$E6E50BC2-190C-4A08-8D99-FBC03C3C565B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86f1036f52c9d084642933ae13a25638be140f18","datavalue":{"value":{"entity-type":"item","numeric-id":3039039,"id":"Q3039039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$4B50F005-26DD-4BD4-B27B-AD9C42957345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9b4b0263bf157bc56ee9f4278362c292a571a65","datavalue":{"value":{"entity-type":"item","numeric-id":1147168,"id":"Q1147168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$C1431F86-8E10-49C8-BAE0-A1FDBD03636B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8ee1234db0900b559e8bae74798380dbb17ec89","datavalue":{"value":{"entity-type":"item","numeric-id":1330903,"id":"Q1330903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$DB0ADCE2-C285-426D-92DB-36310563A258","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9e8a2a2ba09a34750ac91787a928d451826bfdc","datavalue":{"value":{"entity-type":"item","numeric-id":3675933,"id":"Q3675933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$BFA83338-59B9-4FAF-8330-495C4A334895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df25916ae88cfd882e8cb6b5b5569c6957043ab0","datavalue":{"value":{"entity-type":"item","numeric-id":2394739,"id":"Q2394739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$8325EFF1-A11C-4A3B-80FC-30793A999256","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c46f17a2d874b1825da8e5176316d6645e368cf4","datavalue":{"value":{"entity-type":"item","numeric-id":3787806,"id":"Q3787806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$6A0062A2-0F50-479E-95C8-5A50F7C529D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb97aa0ae022d4dc38b27f53ae16228cc4072891","datavalue":{"value":{"entity-type":"item","numeric-id":5684698,"id":"Q5684698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$0173D761-10D7-410A-B5EC-0B76108DA33A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42a8fbca1e3fee013ba3a834d1bb5d1f8a9a9af9","datavalue":{"value":{"entity-type":"item","numeric-id":1329787,"id":"Q1329787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$5DB3C238-8B69-44DA-91AA-97F699FB64F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d68ed8ac0fd6d3d2473f5b32417c5b38f6eba1e","datavalue":{"value":{"entity-type":"item","numeric-id":5285475,"id":"Q5285475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$3DAFE5F3-B5AF-4D00-A45F-634728D0FC87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78fd4f6584b73e4f130f3d27f642668b98d41e4f","datavalue":{"value":{"entity-type":"item","numeric-id":4193501,"id":"Q4193501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$2BA245C5-2EAA-4D60-9595-3AC579F94294","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5006347fb0807d0501b25d6ef68cc9327e1f8cf5","datavalue":{"value":{"entity-type":"item","numeric-id":1106858,"id":"Q1106858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$FC7EDC8E-4571-4FF6-A283-F579904038B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff62a58edafa8a8af4a3a1ac64cba69bbc85c85","datavalue":{"value":{"entity-type":"item","numeric-id":1330901,"id":"Q1330901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$BC4527AC-3024-46CB-AF93-FB2F82AE2313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1e8c199d0a3738b5df7039fa423628b9c9f24f","datavalue":{"value":{"entity-type":"item","numeric-id":4040221,"id":"Q4040221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$0A9F03CF-0557-49A1-BACB-395CBCF7489F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5d2ff8ca55c71a00eb97ded234e95c181b7889c","datavalue":{"value":{"entity-type":"item","numeric-id":5603745,"id":"Q5603745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$2DA5A75E-9CF9-45C0-9190-51AA54B69B29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d242372ba09b4d0d4cd4aeddcb0eb809fe66c3a","datavalue":{"value":{"entity-type":"item","numeric-id":3789370,"id":"Q3789370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$29B6C154-57FE-4B2A-A6C8-B39C66CB6161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c71680a4ab9e1f4beb0d4c1abad68c079fb9c955","datavalue":{"value":{"entity-type":"item","numeric-id":3945592,"id":"Q3945592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$B77A9DB3-30CB-4BB9-A47F-0E13F6E16198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8dfff1846e7e39c81f69451d2c8f09c9aca2db6","datavalue":{"value":{"entity-type":"item","numeric-id":3781793,"id":"Q3781793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$DE868387-FD23-4200-BF4C-4F2F39AC3B21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad9cfae9fc9d02b6b7648a5f38f2a07226c5c18d","datavalue":{"value":{"entity-type":"item","numeric-id":3311677,"id":"Q3311677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$4F347B7F-10EA-40B7-8CA3-BA2FA8A2FCA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"540ff49c129c9031c72045385542e8469e7e064b","datavalue":{"value":{"entity-type":"item","numeric-id":3762228,"id":"Q3762228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$15763982-3671-4113-8411-4B2675385D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0650311eaf58d9e1d131a542ba976b8f0f792dfc","datavalue":{"value":{"entity-type":"item","numeric-id":3315294,"id":"Q3315294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322552$EEDEE093-4089-4CAA-BE3A-EC222B4FF385","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77213d5036e5c2700b0f92edf233c6290789bed8","datavalue":{"value":{"entity-type":"item","numeric-id":1330902,"id":"Q1330902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9c03cafa32a3e0df114bf6046fe40a18483e740","datavalue":{"value":{"amount":"+0.8784080147743225","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":"Q1322552$DE8610A9-4047-4237-901D-303C5296F66A","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":"e232a8afaee0087cb9bbdfd681535a48b9373f02","datavalue":{"value":{"amount":"+0.8667212724685669","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":"Q1322552$0723B1D0-371E-437E-908B-C0AD8414A2A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35d686a3f7dab7839df4476d7c7047f8b78d4874","datavalue":{"value":{"entity-type":"item","numeric-id":1330903,"id":"Q1330903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e25f4517a9878830ba23dbc1770f7699de8c74bd","datavalue":{"value":{"amount":"+0.8442414999008179","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":"Q1322552$24881E08-019E-4060-8606-48FF2CD47F57","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Steiner tree polytope and related polyhedra","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Steiner_tree_polytope_and_related_polyhedra"}}}}}