{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:35:03Z","timestamp":1742384103992},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1989,6,1]],"date-time":"1989-06-01T00:00:00Z","timestamp":612662400000},"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":[[1989,6]]},"DOI":"10.1007\/bf01553886","type":"journal-article","created":{"date-parts":[[2005,4,20]],"date-time":"2005-04-20T22:07:35Z","timestamp":1114034855000},"page":"191-207","source":"Crossref","is-referenced-by-count":38,"title":["Fast heuristic algorithms for rectilinear steiner trees"],"prefix":"10.1007","volume":"4","author":[{"given":"Dana","family":"Richards","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF01553886_CR1","unstructured":"P. K. Agarwal and M. T. Shing, Algorithms for the Special Cases of Rectilinear Steiner Trees: I. Points on the Boundary of a Rectilinear Rectangle, Technical Report TRCS86-17, University of California at Santa Barbara, 1986."},{"key":"BF01553886_CR2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1002\/net.3230070104","volume":"7","author":"A. V. Aho","year":"1977","unstructured":"A. V. Aho, M. R. Garey, and F. K. Hwang, Rectilinear Steiner Trees: Efficient Special-Case Algorithms,Networks,7, 1977, pp. 37\u201358.","journal-title":"Networks"},{"key":"BF01553886_CR3","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1002\/net.3230140112","volume":"14","author":"J. E. Beasley","year":"1984","unstructured":"J. E. Beasley, An Algorithm for the Steiner Problem in Graphs,Networks,14, 1984, pp. 147\u2013159.","journal-title":"Networks"},{"key":"BF01553886_CR4","unstructured":"M. W. Bern and M. de Carvalho, A Greedy Heuristic for the Rectilinear Steiner Tree Problem, Technical Report, Computer Science Division, University of California at Berkeley, 1985."},{"key":"BF01553886_CR5","unstructured":"M. W. Bern, A More General Special Case of the Steiner Tree Problem, Technical Report, Computer Science Division, University of California at Berkeley, 1986."},{"key":"BF01553886_CR6","doi-asserted-by":"crossref","unstructured":"M. W. Bern, Two Probabilistic Results on Rectilinear Steiner Trees,Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 433\u2013441. (Corrected version available.)","DOI":"10.1145\/12130.12175"},{"key":"BF01553886_CR7","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230090103","volume":"9","author":"F. R. K. Chung","year":"1979","unstructured":"F. R. K. Chung and F. K. Hwang, The Largest Minimal Rectilinear Steiner Trees for a Set ofn Points Enclosed in a Rectangle with Given Perimeter,Networks,9, 1979, pp. 19\u201336.","journal-title":"Networks"},{"key":"BF01553886_CR8","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 Point Sets,Geometriae Dedicata,11, 1981, pp. 353\u2013361.","journal-title":"Geometriae Dedicata"},{"key":"BF01553886_CR9","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0020-0190(86)90062-1","volume":"22","author":"E. J. Cockayne","year":"1986","unstructured":"E. J. Cockayne and E. E. Hewgill, Exact Computation on Steiner Minimal Trees in the Plane,Information Processing Letters,22, 1986, pp. 151\u2013156.","journal-title":"Information Processing Letters"},{"key":"BF01553886_CR10","unstructured":"A. E. Dunlop, personal communication, 1986."},{"key":"BF01553886_CR11","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"L. R. Foulds","year":"1982","unstructured":"L. R. Foulds and R. L. Graham, The Steiner Problem in Phylogeny is NP-Complete,Advances in Applied Mathematics,3, 1982, pp. 43\u201349.","journal-title":"Advances in Applied Mathematics"},{"key":"BF01553886_CR12","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1080\/03052158308960625","volume":"7","author":"L. R. Foulds","year":"1983","unstructured":"L. R. Foulds and V. J. Rayward-Smith, Steiner Problems in Graphs: Algorithms and Applications,Engineering Optimization,7, 1983, pp. 7\u201316.","journal-title":"Engineering Optimization"},{"key":"BF01553886_CR13","unstructured":"Y. Fu, Application of Linear Graph Theory to Printed Circuits,Proceedings of the Asilomar Conference on Systems and Circuits, 1967, pp. 721\u2013728."},{"key":"BF01553886_CR14","volume-title":"Computers and Intractability","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability, Freeman, San Francisco, 1979."},{"key":"BF01553886_CR15","first-page":"376","volume":"13","author":"E. N. Gilbert","year":"1965","unstructured":"E. N. Gilbert, Random Minimal Trees,SIAM Journal,13, 1965, pp. 376\u2013387.","journal-title":"SIAM Journal"},{"key":"BF01553886_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E. N. Gilbert","year":"1968","unstructured":"E. N. Gilbert and H. O. Pollack, Steiner Minimal Trees,SIAM Journal on Applied Mathematics,16, 1968, pp. 1\u201329.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"BF01553886_CR17","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R. L. Graham","year":"1985","unstructured":"R. L. Graham and P. Hell, On the History of the Minimum Spanning Tree Problem,Annals of the History of Computing,7, 1985, pp. 43\u201357.","journal-title":"Annals of the History of Computing"},{"key":"BF01553886_CR18","unstructured":"M. Hanan, Net Wiring for Large Scale Integrated Circuits, RC 1375, IBM Research Report, 1965."},{"key":"BF01553886_CR19","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 Journal on Applied Mathematics,14, 1966, pp. 255\u2013265.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"BF01553886_CR20","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1109\/TCT.1972.1083408","volume":"19","author":"M. Hanan","year":"1972","unstructured":"M. Hanan, A Counterexample to a Theorem of Fu on Steiner's Problem,IEEE Transactions on Circuit Theory,19, 1972, p. 74.","journal-title":"IEEE Transactions on Circuit Theory"},{"key":"BF01553886_CR21","first-page":"144","volume-title":"VLSI Circuit Layout: Theory and Design","author":"T. C. Hu","year":"1985","unstructured":"T. C. Hu and M. T. Shing, A Decomposition Algorithm for Circuit Routing, inVLSI Circuit Layout: Theory and Design, T. C. Hu and E. S. Kuh (eds.), IEEE Press, New York, 1985, pp. 144\u2013152."},{"key":"BF01553886_CR22","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 Journal on Applied Mathematics,30, 1976, pp. 104\u2013114.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"BF01553886_CR23","first-page":"303","volume":"3","author":"F. K. Hwang","year":"1978","unstructured":"F. K. Hwang, The Rectilinear Steiner Problem,Design Automation & Fault Tolerant Computing,3, 1978, pp. 303\u2013310.","journal-title":"Design Automation & Fault Tolerant Computing"},{"key":"BF01553886_CR24","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TCS.1979.1084551","volume":"26","author":"F. K. Hwang","year":"1979","unstructured":"F. K. Hwang, AnO(n logn) Algorithm for Suboptimal Rectilinear Steiner Trees,IEEE Transactions on Circuits and Systems,26, 1979, pp. 75\u201377.","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"BF01553886_CR25","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,Journal of the ACM,26, 1979, pp. 177\u2013182.","journal-title":"Journal of the ACM"},{"key":"BF01553886_CR26","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0167-6377(86)90008-8","volume":"4","author":"F. K. Hwang","year":"1986","unstructured":"F. K. Hwang, A Linear Time Algorithm for Full Steiner Trees,Operations Research Letters,4, 1986, pp. 235\u2013237.","journal-title":"Operations Research Letters"},{"key":"BF01553886_CR27","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0012-365X(86)90040-3","volume":"62","author":"F. K. Hwang","year":"1986","unstructured":"F. K. Hwang and J. F. Weng, Hexagonal Coordinate Systems and Steiner Minimal Trees,Discrete Mathematics,62, 1986, pp. 49\u201357.","journal-title":"Discrete Mathematics"},{"key":"BF01553886_CR28","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1002\/net.3230150403","volume":"15","author":"J. Komlos","year":"1985","unstructured":"J. Komlos and M. T. Shing, Probabilistic Partitioning Algorithms for the Rectilinear Steiner Problem,Networks,15, 1985, pp. 413\u2013423.","journal-title":"Networks"},{"key":"BF01553886_CR29","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00288961","volume":"15","author":"L. Kou","year":"1981","unstructured":"L. Kou, G. Markowsky and L. Berman, A Fast Algorithm for Steiner Trees,Acta Informatica,15, 1981, pp. 141\u2013145.","journal-title":"Acta Informatica"},{"key":"BF01553886_CR30","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1109\/TCS.1976.1084243","volume":"23","author":"J. H. Lee","year":"1976","unstructured":"J. H. Lee, N. K. Bose, and F. K. Hwang, Use of Steiner's Problem in Suboptimal Routing in Rectilinear Metric,IEEE Transactions on Circuits and Systems,23, 1976, pp. 470\u2013476.","journal-title":"IEEE Transactions on Circuits and Systems"},{"key":"BF01553886_CR31","first-page":"1477","volume":"12","author":"A. J. Levin","year":"1971","unstructured":"A. J. Levin, Algorithm for the Shortest Connection of a Group of Graph Vertices,Soviet Mathematics Doklady,12, 1971, pp. 1477\u20131481.","journal-title":"Soviet Mathematics Doklady"},{"key":"BF01553886_CR32","volume-title":"The Analysis of Algorithms","author":"P. W. Purdom","year":"1985","unstructured":"P. W. Purdom and C. A. Brown,The Analysis of Algorithms, Holt, Rinehart and Winston, New York, 1985."},{"key":"BF01553886_CR33","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1080\/0020739830140103","volume":"14","author":"V. J. Rayward-Smith","year":"1983","unstructured":"V. J. Rayward-Smith, The Computation of Nearly Minimal Steiner Trees in Graphs,International Journal of Mathematical Education in Science and Technology,14, 1983, pp. 15\u201323.","journal-title":"International Journal of Mathematical Education in Science and Technology"},{"key":"BF01553886_CR34","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1002\/net.3230160305","volume":"16","author":"V. J. Rayward-Smith","year":"1986","unstructured":"V. J. Rayward-Smith and A. Clare, On Finding Steiner Vertices,Networks,16, 1986, pp. 283\u2013294.","journal-title":"Networks"},{"key":"BF01553886_CR35","first-page":"21","volume":"7","author":"M. Servit","year":"1981","unstructured":"M. Servit, Heuristic Algorithms for Rectilinear Steiner Trees,Digital Processes,7, 1981, pp. 21\u201332.","journal-title":"Digital Processes"},{"key":"BF01553886_CR36","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/net.3230120309","volume":"12","author":"M. L. Shore","year":"1982","unstructured":"M. L. Shore, L. R. Foulds, and P. B. Gibbons, An Algorithm for the Steiner Problem in Graphs,Networks,12, 1982, pp. 323\u2013333.","journal-title":"Networks"},{"key":"BF01553886_CR37","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1080\/03052157908902401","volume":"4","author":"J. M. Smith","year":"1979","unstructured":"J. M. Smith and J. S. Liebman, Steiner Trees, Steiner Circuits and the Interference Problem in Building Design,Engineering Optimization,4, 1979, pp. 15\u201336.","journal-title":"Engineering Optimization"},{"key":"BF01553886_CR38","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1080\/03052158008902421","volume":"4","author":"J. M. Smith","year":"1980","unstructured":"J. M. Smith, D. T. Lee, and J. S. Liebman, AnO(N logN) Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem,Engineering Optimization,4, 1980, pp. 179\u2013192.","journal-title":"Engineering Optimization"},{"key":"BF01553886_CR39","first-page":"573","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"H. Takahashi and A. Matsuyama, An Approximate Solution for the Steiner Problem in Graphs,Mathematica Japonica,24, 1980, pp. 573\u2013577.","journal-title":"Mathematica Japonica"},{"key":"BF01553886_CR40","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan,Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983."},{"key":"BF01553886_CR41","unstructured":"J. A. Wald and C. J. Colbourn, Steiner Trees in Outerplanar Graphs,Proceedings of the 13th S.E. Conference on Combinatorics, Graph Theory, and Computing, 1982, pp. 15\u201322."},{"key":"BF01553886_CR42","first-page":"241","volume-title":"Advanced Research in VLSI","author":"T. Whitney","year":"1986","unstructured":"T. Whitney and C. Mead, An Integer-Based Hierarchical Representation for VLSI, inAdvanced Research in VLSI, C. E. Leiserson (ed.), MIT Press, Cambridge, MA, 1986, pp. 241\u2013257."},{"key":"BF01553886_CR43","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF00289500","volume":"23","author":"Y. F. Wu","year":"1986","unstructured":"Y. F. Wu, P. Widmayer, and C. K. Wong, A Faster Approximation Algorithm for the Steiner Problem in Graphs,Acta Informatica,23, 1986, pp. 223\u2013229.","journal-title":"Acta Informatica"},{"key":"BF01553886_CR44","unstructured":"Y. Y. Yang and O. Wing, Optimal and Suboptimal Solution Algorithms for the Wiring Problem,Proceedings of the International Symposium on Circuit Theory, 1972, pp. 154\u2013158."},{"key":"BF01553886_CR45","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1109\/TCT.1972.1083538","volume":"19","author":"Y. Y. Yang","year":"1972","unstructured":"Y. Y. Yang and O. Wing, Suboptimal Algorithm for a Wire Routing Problem,IEEE Transactions on Circuit Theory,19, 1972, pp. 508\u2013510.","journal-title":"IEEE Transactions on Circuit Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553886.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01553886\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553886","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T14:21:13Z","timestamp":1556893273000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01553886"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,6]]},"references-count":45,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1989,6]]}},"alternative-id":["BF01553886"],"URL":"https:\/\/doi.org\/10.1007\/bf01553886","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,6]]}}}