{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:28:40Z","timestamp":1787340520696,"version":"build-2736575974"},"reference-count":13,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1983,8]]},"abstract":"<jats:p>Programs for integrated circuit layout typically have two phases; placement and routing. The router tries to produce as efficient a layout as possible, but of course the quality of the routing depends heavily on the quality of the placement. On the other hand, the placement procedure ideally should know the impact of its placement decisions on the quality of a routing. In this paper, we present a placement-and-routing problem for which there is perfect interaction between the two phases. The algorithms for this commonly arising problem are fast, simple and optimal.<\/jats:p>\n                  <jats:p>River routing is the problem of connecting in order a set of terminals $a_1 , \\cdots ,a_n $ on a line to another set $b_1 , \\cdots ,b_n $ across a rectangular channel. The terminals are located on modules which must be placed relative to one another before routing. This placement-and-routing problem arises frequently in design systems like bristle-blocks where stretch lines through a module can effectively break it into several chunks, each of which may be placed separately. In this paper we give concise necessary and sufficient conditions for wirability which are applied to reduce the optimal placement problem to the graph-theoretic single-source-longest-paths problem. For rectilinear wiring, the special structure of graphs that arise allows an optimal solution to be determined quickly.<\/jats:p>","DOI":"10.1137\/0212029","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:05:53Z","timestamp":1109225153000},"page":"447-462","source":"Crossref","is-referenced-by-count":45,"title":["Optimal Placement for River Routing"],"prefix":"10.1137","volume":"12","author":[{"given":"Charles E.","family":"Leiserson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ron Y.","family":"Pinter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","unstructured":"A. E. Baratz, Masters Thesis,  Algorithms for integrated circuit signal routing, Ph.D. dissertation, Dept. Electrical Engineering\/Computer Science, Massachusetts Institute of Technology, Cambridge,  1981, August"},{"key":"R2","unstructured":"I. Batali, N. Mayle, H. Shrobe, G. Sussman, D. Weise,  The DPL \/Daedalus design environment,  Proc. International Conference on VLSI, Univ. of Edinburgh,  1981,  183\u2013192, August"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"D. Dolev, K. Karplus, A. Siegel, A. Strong, J. D. Ullman,  Optimal wiring between rectangles,  Proc. Thirteenth Annual ACM Symposium on Theory of Computing,  1981,  312\u2013317, May","DOI":"10.1145\/800076.802484"},{"key":"R4","unstructured":"M.Y. Hsueh,  Symbolic layout and compaction of integrated circuits, Memo, UCB\/ERL-M79\/80, Electronics Research Laboratory, Univ. California, Berkeley,  1979, Ph.D. dissertation, December"},{"key":"#cr-split#-R5.1","unstructured":"D. L. Johannsen, Silicon compilation, Technical Report, 4530, Dept. Computer Science, California Institute of Technology, Pasadena, CA, 1981, Ph.D. dissertation"},{"key":"#cr-split#-R5.2","doi-asserted-by":"crossref","unstructured":"An overview appears as Bristle blocks: a silicon compiler, in the Proc. of the Sixteenth Design Automation Conference, June 1979, pp. 310-313","DOI":"10.1109\/DAC.1979.1600125"},{"key":"R6","volume-title":"Combinatorial optimization: networks and matroids","author":"Lawler Eugene L.","year":"1976"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"R. Y. Pinter,  On routing two-point nets across a channel,  Proc. Nineteenth Design Automation Conference,  1982,  894\u2013902, June","DOI":"10.1109\/DAC.1982.1585599"},{"key":"R8","unstructured":"R. Y. Pinter, Masters Thesis,  The impact of layer assignment methods on layout algorithms for integrated circuits, Ph.D. dissertation, Dept. Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge,  1982, August"},{"key":"R9","unstructured":"H. E. Shrobe,  The data path generator,  Proc. Conference on Advanced Research in VLSI, Massachusetts Institute of Technology, Cambridge,  1982,  175\u2013181, January"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"A. Siegel, D. Dolev,  The separation for general single-layer wiring barriers,  Proc. CMU Conference on VSLI Systems and Computations,  1981,  143\u2013152, October","DOI":"10.1007\/978-3-642-68402-9_17"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"M. Tompa,  An optimal solution to a wire-routing problem,  Proc. Twelfth Annual Symposium on Theory of Computing,  1980,  161\u2013176, April-May","DOI":"10.1145\/800141.804664"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/253822"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0212029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:54Z","timestamp":1787337474000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0212029"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,8]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1983,8]]}},"alternative-id":["10.1137\/0212029"],"URL":"https:\/\/doi.org\/10.1137\/0212029","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,8]]}}}