{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T01:08:13Z","timestamp":1777597693222,"version":"3.51.4"},"reference-count":23,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2016,11,25]],"date-time":"2016-11-25T00:00:00Z","timestamp":1480032000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2017,1]]},"abstract":"<jats:p>In this article, we consider the Node\u2010Weighted Dominating Steiner Problem. Given a graph with node weights and a set of terminal nodes, the goal is to find a connected node\u2010induced subgraph of minimum weight, such that each terminal node is contained in or adjacent to some node in the chosen subgraph. The problem arises in applications in the design of telecommunication networks. Integer programming formulations for Steiner problems usually employ a variable for each edge. We introduce a formulation that only uses node variables and that models connectivity through node\u2010cut inequalities, which can be separated in polynomial time. We discuss necessary and sufficient conditions for the model inequalities to define facets and we introduce a class of lifted partition\u2010based inequalities, which can be used to strengthen the linear relaxation. Finally, we show that the polyhedron defined by these inequalities is integral if the underlying graph is a cycle where no two terminals are adjacent. In the general cycle setting, we show that we can get a complete description of the feasible solutions by lifting and projecting into a polytope with no more than twice the dimension. We also show that the well\u2010known indegree equalities are implied by the lifted partition inequalities. Finally, we evaluate the effectiveness of the presented partition inequalities in computational experiments. \u00a9 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 33\u201351 2017<\/jats:p>","DOI":"10.1002\/net.21722","type":"journal-article","created":{"date-parts":[[2016,11,25]],"date-time":"2016-11-25T06:28:43Z","timestamp":1480055323000},"page":"33-51","source":"Crossref","is-referenced-by-count":3,"title":["A node\u2010based ILP formulation for the node\u2010weighted dominating Steiner problem"],"prefix":"10.1002","volume":"69","author":[{"given":"Andreas","family":"Bley","sequence":"first","affiliation":[{"name":"Department of Mathematics Universitat Kassel Kassel Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivana","family":"Ljubi\u0107","sequence":"additional","affiliation":[{"name":"ESSEC Business School of Paris Cergy\u2010Pontoise France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Olaf","family":"Maurer","sequence":"additional","affiliation":[{"name":"Department of Mathematics Universitat Kassel Kassel Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2016,11,25]]},"reference":[{"key":"e_1_2_8_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38189-8_11"},{"key":"e_1_2_8_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90086-6"},{"key":"e_1_2_8_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1183"},{"key":"e_1_2_8_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90029-1"},{"key":"e_1_2_8_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582573"},{"key":"e_1_2_8_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_28"},{"key":"e_1_2_8_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_8_9_1","first-page":"1","article-title":"Thinning out Steiner trees: A node based model for uniform edge costs","author":"Fischetti M.","year":"2016","journal-title":"Math Program Comput"},{"key":"e_1_2_8_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20001"},{"key":"e_1_2_8_11_1","volume-title":"Computers and intractability\u2014A guide to the theory of NP\u2010completeness","author":"Garey M.R.","year":"1979"},{"key":"e_1_2_8_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"e_1_2_8_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2013.0589"},{"key":"e_1_2_8_14_1","unstructured":"B.V.CherasskyandA.V.Goldberg On implementing push-relabel method for the maximum flow problem Tech. Report 1994. Implementation available at:https:\/\/2.zoppoz.workers.dev:443\/http\/www.avglab.com\/andrew\/soft.html."},{"key":"e_1_2_8_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009201"},{"key":"e_1_2_8_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2754"},{"key":"e_1_2_8_17_1","doi-asserted-by":"crossref","unstructured":"E.HalperinandR.Krauthgamer \u201cPolylogarithmic inapproximability.\u201d Proceedings of the 35th Annual ACM Symposium on Theory of Computing ACM New York 2003 pp.585\u2013594.","DOI":"10.1145\/780542.780628"},{"key":"e_1_2_8_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(86)90089-2"},{"key":"e_1_2_8_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.08.021"},{"key":"e_1_2_8_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1029"},{"key":"e_1_2_8_21_1","volume-title":"SteinLib: An updated library on Steiner tree problems in graphs. Tech. Rep. ZIB\u2010Report 00\u201037. Takustr. 7","author":"Koch T.","year":"2000"},{"key":"e_1_2_8_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58191-5"},{"key":"e_1_2_8_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.013"},{"key":"e_1_2_8_24_1","unstructured":"Y.Wang A.Buchanan andS.Butenko On imposing connectivity constraints in integer programs Optimization Online 2015 Available at:www.optimization-online.org\/DB_HTML\/2015\/02\/4768.html(access 10.9.2016)."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.21722","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.21722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T20:05:59Z","timestamp":1694635559000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/net.21722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,25]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["10.1002\/net.21722"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/net.21722","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,25]]}}}