{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:40:05Z","timestamp":1771026005319,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1997,8,1]],"date-time":"1997-08-01T00:00:00Z","timestamp":870393600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1997,8]]},"DOI":"10.1007\/bf02614374","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T04:34:50Z","timestamp":1177734890000},"page":"265-281","source":"Crossref","is-referenced-by-count":50,"title":["The steiner tree packing problem in VLSI design"],"prefix":"10.1007","volume":"78","author":[{"given":"M.","family":"Gr\u00f6tschel","sequence":"first","affiliation":[]},{"given":"A.","family":"Martin","sequence":"additional","affiliation":[]},{"given":"R.","family":"Weismantel","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02614374_CR1","first-page":"245","volume-title":"Advances in Computing Research, Vol. 2: VLSI theory","author":"M.L. Brady","year":"1984","unstructured":"M.L. Brady and D.J. Brown, \u201cVLSI routing: Four layers suffice,\u201d in: F.P. Preparata, ed.,Advances in Computing Research, Vol. 2: VLSI theory (Jai Press, London, 1984) 245\u2013258."},{"key":"BF02614374_CR2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1109\/TCAD.1983.1270040","volume":"CAD-2","author":"M. Burstein","year":"1983","unstructured":"M. Burstein and R. Pelavin, \u201cHierarchical wire routing,\u201dIEEE Transactions on Computer-Aided-Design CAD-2 (1983) 223\u2013234.","journal-title":"IEEE Transactions on Computer-Aided-Design"},{"key":"BF02614374_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, \u201cThe rectilinear Steiner tree problem isNP-complete,\u201dSIAM J. Appl. Math. 32 (1977) 826\u2013834.","journal-title":"SIAM J. Appl. Math."},{"key":"BF02614374_CR4","doi-asserted-by":"crossref","first-page":"684","DOI":"10.1109\/43.3208","volume":"CAD-7","author":"J.P. Cohoon","year":"1988","unstructured":"J.P. Cohoon and P.L. Heck, \u201cBEAVER: A computational-geometry-based tool for switchbox routing,\u201dIEEE Transactions on Computer-Aided-Design CAD-7 (1988) 684\u2013697.","journal-title":"IEEE Transactions on Computer-Aided-Design"},{"key":"BF02614374_CR5","doi-asserted-by":"crossref","first-page":"1350","DOI":"10.1109\/43.44515","volume":"CAD-8","author":"S.H. Gerez","year":"1989","unstructured":"S.H. Gerez and O.E. Herrmann, \u201cSwitchbox routing by stepwise reshaping,\u201dIEEE Transactions on Computer-Aided-Design CAD-8 (1989) 1350\u20131361.","journal-title":"IEEE Transactions on Computer-Aided-Design"},{"key":"BF02614374_CR6","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1137\/0403043","volume":"3","author":"M. Gr\u00f6tschel","year":"1990","unstructured":"M. Gr\u00f6tschel and C.L. Monma, \u201cInteger polyhedra associated with certain network design problems with connectivity constraints,\u201dSIAM Journal on Discrete Mathematics 3 (1990) 502\u2013523.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"BF02614374_CR7","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF02592085","volume":"72","author":"M. Gr\u00f6tschel","year":"1996","unstructured":"M. Gr\u00f6tschel, A. Martin and R. Weismantel, \u201cPacking Steiner trees: polyhedral investigations,\u201dMathematical Programming 72 (1996) 101\u2013124.","journal-title":"Mathematical Programming"},{"key":"BF02614374_CR8","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF02592086","volume":"72","author":"M. Gr\u00f6tschel","year":"1996","unstructured":"M. Gr\u00f6tschel, A. Martin and R. Weismantel, \u201cPacking Steiner trees: a cutting plane algorithm and computational results,\u201dMathematical Programming 72 (1996) 125\u2013146.","journal-title":"Mathematical Programming"},{"issue":"2","key":"BF02614374_CR9","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1137\/S0895480193258716","volume":"9","author":"M. Gr\u00f6tschel","year":"1996","unstructured":"M. Gr\u00f6tschel, A. Martin and R. Weismantel, \u201cPacking Steiner trees: separation algorithms,\u201dSIAM Journal on Discrete Mathematics 9 (2) (1996) 233\u2013257.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"BF02614374_CR10","doi-asserted-by":"crossref","unstructured":"J.M. Jou, J.Y. Lee, Y. Sun and J.F. Wang, \u201cAn efficient VLSI switch-box router,\u201dIEEE Design and Test (1990) 52\u201365.","DOI":"10.1109\/54.57914"},{"key":"BF02614374_CR11","unstructured":"R. Joobbani and D.P. Siewiorek, \u201cWEAVER: A knowledge-based routing expert,\u201dIEEE Design and Test (1986) 12\u201323."},{"key":"BF02614374_CR12","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, \u201cReducibility among combinatorial problems,\u201d in: R.E. Miller and J.W. Thatcher, eds.,Complexity of Computer Computations (Plenum Press, New York, 1972) 85\u2013103."},{"key":"BF02614374_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial algorithms for integrated circuit layout","author":"T. Lengauer","year":"1990","unstructured":"T. Lengauer,Combinatorial algorithms for integrated circuit layout (Wiley, Chichester, 1990)."},{"key":"BF02614374_CR14","unstructured":"Y.L. Lin, Y.C. Hsu and F.S. Tsai, \u201cA detailed router based on simulated evolution,\u201d in:Proc. Int. Conf. Computer-Aided-Design, 1988, 38\u201341."},{"key":"BF02614374_CR15","first-page":"231","volume-title":"Advances in Computing Research","author":"W. Lipski","year":"1984","unstructured":"W. Lipski, \u201cOn the structure of three-layer wireable layouts,\u201d F.P. Preparata, ed.,Advances in Computing Research, Vol. 2:VLSI theory (Jai Press, London, 1984) 231\u2013244."},{"key":"BF02614374_CR16","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0167-9260(85)90029-X","volume":"3","author":"W.K. Luk","year":"1985","unstructured":"W.K. Luk, \u201cA greedy switch-box router,\u201dIntegration 3 (1985) 129\u2013149.","journal-title":"Integration"},{"key":"BF02614374_CR17","unstructured":"A. Martin, \u201cPacken von Steinerb\u00e4umen: Polyedrische Studien und Anwendung,\u201d Ph.D. Thesis, Technische Universit\u00e4t Berlin, 1992."},{"key":"BF02614374_CR18","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1109\/TCAD.1987.1270298","volume":"CAD-6","author":"M. Sarrafzadeh","year":"1987","unstructured":"M. Sarrafzadeh, \u201cChannel-routing problem in the knock-knee mode isNP-complete,\u201dIEEE Transactions on Computer-Aided-Design CAD-6 (1987) 503\u2013506.","journal-title":"IEEE Transactions on Computer-Aided-Design"},{"key":"BF02614374_CR19","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/TCAD.1985.1270096","volume":"CAD-4","author":"T.G. Szymanski","year":"1985","unstructured":"T.G. Szymanski, \u201cDogleg channel routing isNP-complete,\u201dIEEE Transactions on Computer-Aided-Design CAD-4 (1985) 31\u201340.","journal-title":"IEEE Transactions on Computer-Aided-Design"},{"key":"BF02614374_CR20","unstructured":"P. Tzeng and C.H. S\u00e9quin, \u201cCodar: a congestion-directed general area router,\u201d in:Proc. Int. Conf. Computer-Aided Design (1988) 30\u201333."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614374.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02614374\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,21]],"date-time":"2020-04-21T15:39:42Z","timestamp":1587483582000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02614374"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,8]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,8]]}},"alternative-id":["BF02614374"],"URL":"https:\/\/doi.org\/10.1007\/bf02614374","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,8]]}}}