{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:36Z","timestamp":1787340636079,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,2]]},"abstract":"<jats:p>Polynomial algorithms are described that solve the MIN CUT LINEAR ARRANGEMENT problem on degree restricted trees. For example, the cutwidth or folding number of an arbitrary degree d tree can be found in $O(n(\\log n)^{d - 2} )$ steps. This has applications to integrated circuit layout, in particular the layout of Weinberger arrays [41]. This also yields an algorithm for determining the black\/white pebble demand of degree three trees. We also show that for degree three trees, cutwidth is identical to search number and give a forbidden subgraph characterization of degree three trees having cutwidth k.<\/jats:p>","DOI":"10.1137\/0214013","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"158-177","source":"Crossref","is-referenced-by-count":39,"title":["Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees"],"prefix":"10.1137","volume":"14","author":[{"given":"Moon-Jung","family":"Chung","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fillia","family":"Makedon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan Hal","family":"Sudborough","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Turner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","first-page":"343","volume":"1","author":"Breuer M. A.","year":"1977","journal-title":"J. Design Automation and Fault Tolerant Computing"},{"key":"R2","unstructured":"F. R. K. Chung,  On linear arrangements of trees, TM-80-1216-31, Bell Laboratories, Murray Hill, NJ,  1980"},{"key":"R3","first-page":"255","volume-title":"The theory and applications of graphs (Kalamazoo, Mich., 1980)","author":"Chung F. R. K.","year":"1981"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0606026"},{"key":"R5","unstructured":"D. Dolev, H. Trickey,  Embedding a tree on a line, IBM Technical Report, RJ3368,  1982"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Feller,  Automatic layout of low-cost quick turnaround random-logic custom LSI devices,  Proc. Thirteenth Design Automation Conference,  1976,  79\u201385","DOI":"10.1145\/800146.804799"},{"key":"R7","unstructured":"M. J. Foster, H. T. Kung,  Recognizing regular languages with programmable building-blocks,  VLSI-81 Conference,  1981, Aug."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/0134037"},{"key":"R10","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R11","unstructured":"F. Gavril,  Some NP-complete problems on graphs,  Proc. 11th Conference on Information Sciences and Systems, John Hopkins Univ., Baltimore, MD,  91\u201395"},{"key":"R12","unstructured":"M. K. Goldberg, I. A. Klipker,  Minimal placing of trees on a line, Technical Report, Physico-Technical Institute of Low Temperatures, Academy of Sciences of Ukrainian SSR,  1976, (In Russian)"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90006-3"},{"key":"R14","unstructured":"A. S. LaPaugh,  Recontamination does not help, Technical Report, Computer Science Dept., Princeton Univ., Princeton, NJ,  1983"},{"key":"R15","first-page":"1311","author":"Iordanskii M. A.","year":"1974","journal-title":"Soviet Math. Doklady"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264496"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90136-2"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322354"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1137\/0603010"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1109\/T-ED.1980.20086"},{"key":"R21","unstructured":"M. C. Loui,  The space complexity of two pebble games on trees, MIT Technical Report, MIT\/LCS\/TM-133, Massachusetts Institute of Technology, Cambridge,  1979"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036931"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0606044"},{"key":"R24","unstructured":"N. Megiddo,  Linear time algorithm for search number in trees,  1981, unpublished manuscript, April"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"N. Megiddo, S. L. Hakimi, Michael, R. Garey, David, S. Johnson, Christos, H. Papadimitriou,  The complexity of searching a graph,  Proc. IEEE Foundations of Computer Science Symposium,  1981,  376\u2013385","DOI":"10.1109\/SFCS.1981.46"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80004-7"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1109\/TCS.1979.1084695"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Burkhard Monien, I. H. Sudborough,  Bandwidth constrained NP-complete problems,  Proc. 11th ACM Symposium on Theory of Computing,  1981,  207\u2013217","DOI":"10.1145\/800076.802474"},{"key":"R29","volume-title":"Counting labelled trees","author":"Moon John W.","year":"1970"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280884"},{"key":"R31","unstructured":"T. D. Parsons,  The search number of a connected graph,  Proceedings of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1978), Congress. Numer., XXI, Utilitas Math., Winnipeg, Man.,  1978,  549\u2013554 81c:05034"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0070400"},{"key":"R33","first-page":"217","volume":"1","author":"Persky G.","year":"1977","journal-title":"J. Design Automation and Fault Tolerant Computing"},{"key":"R34","unstructured":"N. Pippenger,  Pebbling, RC8258, IBM Research Report,  1980"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"N. Pippenger,  Advances in pebbling, RJ3466, IBM Research Report,  1982","DOI":"10.1007\/BFb0012787"},{"key":"R36","unstructured":"N. Pippenger, private communication"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1145\/362848.362859"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/0208002"},{"key":"R39","unstructured":"L. Stockmeyer,  1974, private communication to M. R. Garey and D. S. Johnson, see [10, p. 201]"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1109\/MSPEC.1982.6366725"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1109\/JSSC.1967.1049816"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"Mihalis Yannakakis,  A polynomial algorithm for the min-cut linear arrangement of trees,  Proc. IEEE Symposium on the Foundations of Computer Science,  1983","DOI":"10.1109\/SFCS.1983.2"},{"key":"R43","unstructured":"H. Yoshizawa, H. Kawanishi, K. Kani,  A heuristic procedure for ordering MOS arrays,  Proc. Design Automation Conference,  1975,  384\u2013393"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214013","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:19Z","timestamp":1787337739000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214013"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,2]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1985,2]]}},"alternative-id":["10.1137\/0214013"],"URL":"https:\/\/doi.org\/10.1137\/0214013","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,2]]}}}