{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:33:34Z","timestamp":1759847614287},"reference-count":19,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2002,10,11]],"date-time":"2002-10-11T00:00:00Z","timestamp":1034294400000},"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":[[2002,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Capacitated Minimum Spanning Tree Problem seeks a least\u2010cost spanning tree subject to a bound imposed on the number of nodes in each subtree pending from a given root node. Araque et al. (Technical Report SOR\u201090\u201012, Princeton University, 1990) introduced several classes of facet\u2010defining inequalities for the undirected version of the problem, most of which have straightforward analogs to the directed version and are also facet\u2010defining in that case (see Zhang, Master's thesis, 1993). The multistar constraints are one such class. Gouveia [Telecommun Syst 1 (1993), 51\u201356] showed that a directed flow formulation gives a polynomial representation of the class of directed multistar constraints. This equivalence shows how to obtain a polynomial\u2010time separation algorithm for this class of inequalities. In this paper, we show that the previous equivalence result implies that we can also separate in polynomial time the exponential\u2010sized class of <jats:italic>undirected<\/jats:italic> multistar constraints. We also show that \u201cusing a directed model\u201d plays a key role in obtaining a polynomial\u2010time separation algorithm for this class of inequalities, that is, using a directed flow model seems to be crucial for obtaining a polynomial\u2010time separation algorithm for the class of undirected multistar constraints. \u00a9 2002 Wiley Periodicals, Inc.<\/jats:p>","DOI":"10.1002\/net.10050","type":"journal-article","created":{"date-parts":[[2002,10,24]],"date-time":"2002-10-24T13:01:35Z","timestamp":1035464495000},"page":"188-201","source":"Crossref","is-referenced-by-count":5,"title":["Multistars and directed flow formulations"],"prefix":"10.1002","volume":"40","author":[{"given":"Luis","family":"Gouveia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie","family":"Hall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2002,10,11]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Network flows: Theory, algorithms and applications","author":"Ahuja R. K.","year":"1994"},{"key":"e_1_2_1_3_2","unstructured":"J. R.Araque L. A.Hall andT. L.Magnanti Capacitated trees capacitated routing and associated polyhedra Technical Report SOR\u201090\u201012 Princeton University 1990."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.37.5.716"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584082"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/322358.322367"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1985.1096250"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230230104"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02136155"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.1.130"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(200001)35:1<1::AID-NET1>3.0.CO;2-L"},{"key":"e_1_2_1_12_2","unstructured":"L. A.Hall Two topics in discrete optimization: Polyhedral structure of capacitated trees and approximation algorithms for scheduling Ph.D. Thesis Operations Research Center The Massachusetts Institute of Technology 1989."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.8.3.219"},{"key":"e_1_2_1_14_2","unstructured":"T.MagnantiandS.Raghavan Strong formulations for network design problems with connectivity requirements Working paper OR 332\u201099 Operations Research Center The Massachusetts Institute of Technology 1999."},{"key":"e_1_2_1_15_2","series-title":"Handbooks in operations research and management science","author":"Magnanti T. L.","year":"1996"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.18.1.1"},{"key":"e_1_2_1_17_2","volume-title":"Integer and combinatorial optimization","author":"Nemhauser G.","year":"1998"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080306"},{"key":"e_1_2_1_19_2","series-title":"Handbooks in operations research and management science","author":"Pulleyblank W.","year":"1989"},{"key":"e_1_2_1_20_2","unstructured":"N.Zhang Facet\u2010defining inequalities for capacitated spanning trees Master's Thesis Princeton University 1993."}],"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.10050","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.10050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,19]],"date-time":"2023-11-19T10:14:04Z","timestamp":1700388844000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/net.10050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10,11]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2002,12]]}},"alternative-id":["10.1002\/net.10050"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/net.10050","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,10,11]]}}}