{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T19:41:31Z","timestamp":1698176491715},"reference-count":29,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":6798,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1988,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the role convexity plays in the efficient solution to the Steiner tree problem. In general terms, we show that a Steiner tree problem is always computationally easier to solve when the points to be connected lie on the boundary of a \u201cconvex\u201d region. For the Steiner tree problem on graphs and the rectilinear Steiner tree problem, we give definitions of \u201cconvexity\u201d for which this condition is sufficient to allow a polynomial algorithm for finding the optimal Steiner tree. For the classical Steiner tree problem, we show that for the standard definition of convexity, this condition is sufficient to allow a fully polynomial approximation scheme.<\/jats:p>","DOI":"10.1002\/net.3230180108","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T23:20:09Z","timestamp":1178925609000},"page":"55-72","source":"Crossref","is-referenced-by-count":47,"title":["Convexity and the Steiner tree problem"],"prefix":"10.1002","volume":"18","author":[{"given":"J.","family":"Scott Provan","sequence":"first","affiliation":[]}],"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.3230070104"},{"key":"e_1_2_1_3_2","unstructured":"D.BienstockandC. L.Monma Optimal enclosing regions in planar graphs. Tech. Report Bell Communication Research Morristown NJ (1986)."},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321733"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70332-7"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/0118014"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.2307\/2045853"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.4.634"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/367766.368168"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/0601010"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132072"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"e_1_2_1_14_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(72)90045-2"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010203"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/0114025"},{"key":"e_1_2_1_19_2","unstructured":"F. K.Hwang G. D.Song G. Y.Ting andD. Z.Hu A decomposition theorem on Euclidean Steiner minimal trees.Discrete and Computational Geometry (toappear)."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0130013"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288961"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1961-016-2"},{"key":"e_1_2_1_24_2","unstructured":"J. S.Provan A polynomial algorithm for the Steiner tree problem on terminal\u2010planar graphs. Tech. Rep. 83\/10 Department of Operations Research University of North Carolina Chapel Hill (1983)."},{"key":"e_1_2_1_25_2","volume-title":"Shortest enclosing walks and cycles in embedded graphs. Tech Rep. 87\/11","author":"Provan J. S.","year":"1987"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120309"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230110104"},{"key":"e_1_2_1_28_2","first-page":"573","article-title":"An approximate solution for the Steiner problem in graphs","volume":"24","author":"Takahashi H.","year":"1980","journal-title":"Math. Japonica"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130202"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321107"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230180108","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230180108","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T20:16:51Z","timestamp":1697919411000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230180108"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,3]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1988,3]]}},"alternative-id":["10.1002\/net.3230180108"],"URL":"https:\/\/doi.org\/10.1002\/net.3230180108","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,3]]}}}