{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:47:28Z","timestamp":1770994048026,"version":"3.50.1"},"reference-count":11,"publisher":"Springer Science and Business Media LLC","issue":"1-6","license":[{"start":{"date-parts":[[1992,6,1]],"date-time":"1992-06-01T00:00:00Z","timestamp":707356800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1992,6]]},"DOI":"10.1007\/bf01758762","type":"journal-article","created":{"date-parts":[[2005,6,15]],"date-time":"2005-06-15T10:49:08Z","timestamp":1118832548000},"page":"277-288","source":"Crossref","is-referenced-by-count":92,"title":["The rectilinear steiner arborescence problem"],"prefix":"10.1007","volume":"7","author":[{"given":"Sailesh K.","family":"Rao","sequence":"first","affiliation":[]},{"given":"P.","family":"Sadayappan","sequence":"additional","affiliation":[]},{"given":"Frank K.","family":"Hwang","sequence":"additional","affiliation":[]},{"given":"Peter W.","family":"Shor","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01758762_CR1","first-page":"353","volume":"11","author":"F. R. K. Chung","year":"1981","unstructured":"F. R. K. Chung and R. L. Graham, On Steiner trees for bounded sets,Geom. Dedicata 11 (1981), 353\u2013361.","journal-title":"Geom. Dedicata"},{"key":"BF01758762_CR2","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1112\/S0025579300000784","volume":"2","author":"L. Few","year":"1955","unstructured":"L. Few, The shortest path and shortest roads throughn points,Mathematika 2 (1955), 141\u2013144.","journal-title":"Mathematika"},{"key":"BF01758762_CR3","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M. R. Garey","year":"1977","unstructured":"M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete,SIAM J, Appl. Math. 32 (1977), 826\u2013834.","journal-title":"SIAM J, Appl. Math."},{"key":"BF01758762_CR4","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0114025","volume":"14","author":"M. Hanan","year":"1966","unstructured":"M. Hanan, On Steiner's problem with rectilinear distance,SIAM J. Appl. Math. 14 (1966), 255\u2013265.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01758762_CR5","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"F. K. Hwang","year":"1976","unstructured":"F. K. Hwang, On Steiner minimal trees with rectilinear distance,SIAM J. Appl. Math. 30 (1976), 104\u2013114.","journal-title":"SIAM J. Appl. Math."},{"key":"BF01758762_CR6","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/322123.322124","volume":"26","author":"F. K. Hwang","year":"1979","unstructured":"F. K. Hwang, AnO(n logn) algorithm for rectilinear minimal spanning trees,J. Assoc. Comput. Mach. 26 (1979), 177\u2013182.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF01758762_CR7","unstructured":"R. R. Ladeira de Matos, A Rectilinear Arborescence Problem, Dissertation, University of Alabama, 1979."},{"key":"BF01758762_CR8","first-page":"59","volume":"18","author":"L. Nastansky","year":"1974","unstructured":"L. Nastansky, S. M. Selkow, and N. F. Stewart, Cost-minimal trees in directed acyclic graphs,Z. Oper. Res. 18 (1974), 59\u201367.","journal-title":"Z. Oper. Res."},{"key":"BF01758762_CR9","unstructured":"J. S. Provan, A Polynomial Algorithm for the Steiner Tree Problem on Terminal-Planar Graphs, Technical Report UNC\/ORST\/TR-83\/10, University of North Carolina, 1983."},{"key":"BF01758762_CR10","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","volume":"7","author":"R. E. Tarjan","year":"1977","unstructured":"R. E. Tarjan, Finding optimum branchings,Networks 7 (1977), 25\u201335.","journal-title":"Networks"},{"key":"BF01758762_CR11","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF01078826","volume":"21","author":"V. A. Trubin","year":"1985","unstructured":"V. A. Trubin, Subclass of the Steiner problems on a plane with rectilinear metric,Cybernetics 21 (1985), 320\u2013322, translated fromKibernetika 21, No. 3 (1985), 37\u201340.","journal-title":"Cybernetics"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758762.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01758762\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01758762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T16:25:40Z","timestamp":1557332740000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01758762"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,6]]},"references-count":11,"journal-issue":{"issue":"1-6","published-print":{"date-parts":[[1992,6]]}},"alternative-id":["BF01758762"],"URL":"https:\/\/doi.org\/10.1007\/bf01758762","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,6]]}}}