{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T21:06:14Z","timestamp":1781039174388,"version":"3.54.1"},"reference-count":17,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5854,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1990,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this article, we introduce a new integer programming formulation for the minimum Steiner tree problem in directed graphs. With the observation that every Steiner tree contains a two\u2010terminal Steiner tree for every pair of the terminals, our formulation is based on the linear programming formulation for the two terminal Steiner tree polyhedron obtained by Ball et al. [2]. By the results of Ball et al. [2], this formulation contains a large class of facets that are different from those induced by the well\u2010known Steiner cut constraints. We give a general form of the dual ascent algorithm and discuss the relationship between this algorithm and the projection method for extended formulations. This dual ascent algorithm is applied to the new formulation to obtain a lower bound for the minimum Steiner tree problem. In the algorithm, we use the dual ascent algorithm introduced by Wong [16] as a subroutine and improve his lower bound. Some computational results are given in Section 3.<\/jats:p>","DOI":"10.1002\/net.3230200606","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T09:49:20Z","timestamp":1178963360000},"page":"765-778","source":"Crossref","is-referenced-by-count":16,"title":["A lower bound for the steiner tree problem in directed graphs"],"prefix":"10.1002","volume":"20","author":[{"given":"Weiguo","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130405"},{"key":"e_1_2_1_3_2","unstructured":"M. O.Ball W.\u2010G.Liu andW. R.Pullyblank Two terminal Steiner tree polyhedra.Proceedings of CORE 20th Year Anniversary Conference to appear."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140112"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386316"},{"key":"e_1_2_1_6_2","unstructured":"A.ClauseandN.Maculan Une nouvelle formulation du probl\u00e9me de Steiner surun graphe.Publication 280 Centre de Recherche sur les Transports Universit\u00e9 de Montr\u00e9al(1983)."},{"key":"e_1_2_1_7_2","volume-title":"Active Analysis of Production and Allocation","author":"Dantzig G. B.","year":"1951"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_9_2","first-page":"346","volume-title":"Optimum branchings. Mathematics of the Decision Sciences","author":"Edmonds J.","year":"1968"},{"key":"e_1_2_1_9_3","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.032"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010203"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_12_2","unstructured":"W.\u2010G.Liu Extended formulation and polyhedral projection. Ph. D. Thesis the Department of Combinatorics and Optimization University of Waterloo. (1988)."},{"issue":"2","key":"e_1_2_1_13_2","first-page":"53","article-title":"A new linear programming formulation for the shortest s\u2010directed spanning problem","volume":"11","author":"Maculan N.","year":"1986","journal-title":"J. Combinatorics, Information and Syst. Sci."},{"key":"e_1_2_1_14_2","first-page":"185","article-title":"The Steiner problem in graphs","volume":"31","author":"Maculan N.","year":"1987","journal-title":"Ann. Discrete Math."},{"key":"e_1_2_1_15_2","unstructured":"O. I.Palma\u2010PachecoandN.Maculan Heuristic method for the Steiner tree problem in directed graphs (in Portuguese) Proceedings of the III Latin Iberian American Conference on Operations Research and System Engineering(1966)117\u2013140."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170203"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02612335"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230200606","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230200606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T09:26:05Z","timestamp":1697966765000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230200606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,10]]},"references-count":17,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1990,10]]}},"alternative-id":["10.1002\/net.3230200606"],"URL":"https:\/\/doi.org\/10.1002\/net.3230200606","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,10]]}}}