{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:51:30Z","timestamp":1725663090045},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167662"},{"type":"electronic","value":"9783540387466"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16766-8_23","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:53:56Z","timestamp":1330178036000},"page":"252-260","source":"Crossref","is-referenced-by-count":2,"title":["A polynomial algorithm for recognizing small cutwidth in hypergraphs"],"prefix":"10.1007","author":[{"given":"Z.","family":"Miller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I. H.","family":"Sudborough","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"F. R. K. Chung, \"On the Cutwidth and the Topological Bandwidth of a Tree\", SIAM J. Alg. Discrete Meth. (1985).","DOI":"10.1137\/0606026"},{"issue":"5","key":"23_CR2","doi-asserted-by":"crossref","first-page":"626","DOI":"10.1109\/TCS.1974.1083910","volume":"21","author":"I. Cederbaum","year":"1974","unstructured":"I. Cederbaum, \"Optimal Backboard Ordering through the Shortest Path Algorithm\", IEEE Trans. on Circuits and Systems 21,5 (1974), pp. 626\u2013632.","journal-title":"IEEE Trans. on Circuits and Systems"},{"key":"23_CR3","unstructured":"J. Cahoon and S. Sahni, \"Two Algorithms for Special Cases of the Board Permutation Problem\", manuscript"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"J. Cahoon and S. Sahni, \"Heuristics for the Board Permutation Problem\", IEEE Int. Conf. on Computer-Aided Design ( 1983 ), pp. 81\u201383.","DOI":"10.1109\/DAC.1983.1585709"},{"issue":"1","key":"23_CR5","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1137\/0214013","volume":"14","author":"M.-J. Chung","year":"1985","unstructured":"M.-J. Chung, F. Makedon, I. H. Sudborough and J. Turner, \"Polynomial Algorithms for the Min-Cut Linear Arrangement Problem on Degree Restricted Trees\", SIAM J. Computing 14, 1 (1985), pp. 158\u2013177.","journal-title":"SIAM J. Computing"},{"key":"23_CR6","unstructured":"J.A. Ellis, I.H. Subdorough, and J.S. Turner, \"Graph Separation and Search Number\", manuscript, extended abstract in Proc. 1983 Allerton Conf. on Communication, Control, and Computing"},{"key":"23_CR7","unstructured":"Garey, M. R and Johnson, D. S, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, San Francisco (1979)"},{"issue":"11","key":"23_CR8","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1109\/TCS.1977.1084286","volume":"21","author":"S. Goto","year":"1977","unstructured":"S. Goto, I. Cederbaum, and B. S. Ting, \"Suboptimum Solution of the Backboard Ordering Problem with Channel Capacity Constraint\", IEEE Trans. on Circuits and Systems 21, 11 (1977), pp. 645\u2013652.","journal-title":"IEEE Trans. on Circuits and Systems"},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1016\/0196-6774(84)90006-3","volume":"5","author":"E. Gurari","year":"1984","unstructured":"E. Gurari and I. H. Sudborough, \"Improved Dynamic Programming Algorithms for Bandwidth Minimization and the Min Cut Linear Arrangment Problem\", J. Algorithms 5 ( 1984 ), pp. 531\u2013546.","journal-title":"J. Algorithms"},{"key":"23_CR10","unstructured":"J. T. Li, \"Algorithms for Gate Matrix Layout\", Proc. IEEE Int. Symp. on Circuits and Systems ( 1983 ), pp. 1013\u20131016."},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"F. Makedon and I. H. Sudborough, \"Minimizing Width in Linear Layouts\", Proc. 10th ICALP, vol. 154, Lecture Notes in Computer Science, Springer Verlag ( 1983 ), pp. 478\u2013490.","DOI":"10.1007\/BFb0036931"},{"issue":"3","key":"23_CR12","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1137\/0606044","volume":"6","author":"F. Makedon","year":"1985","unstructured":"F. Makedon, C. H. Papadimitriou and I. H. Sudborough, \"Topological Bandwidth\", SIAM J. Alg. Discrete Meth. 6, 3 (1985), pp. 418\u2013444.","journal-title":"SIAM J. Alg. Discrete Meth."},{"key":"23_CR13","unstructured":"N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson and C. H. Papadimitriou, \"The Complexity of Searching a Graph (Preliminary Version)\", Proc. IEEE FOCS (1981), pp. 376\u2013385"},{"key":"23_CR14","unstructured":"Z. Miller, \"A Linear Algorithm for Topological Bandwidth in Degree 3 Trees\", manuscript."},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"B. Monien and I. H. Sudborough, \"Min Cut is NP-Complete for Edge Weighted Trees\", Proc. ICALP '86, to appear.","DOI":"10.1007\/3-540-16761-7_76"},{"issue":"1","key":"23_CR16","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1137\/1003003","volume":"3","author":"L. Steinberg","year":"1961","unstructured":"L. Steinberg, \"The Back Board Wiring Problem: A Placement Algorithm\", SIAM Review 3, 1 ( Jan. 1961 ), pp. 37\u201350.","journal-title":"SIAM Review"},{"key":"23_CR17","unstructured":"A. Sangiovanni-Vincentelli and M. Santomauro, \"A Heuristic Guided Algorithm for Optimal Backboard Wiring\", 13th Annual Allerton Conference on Circuits and Systems ( 1975 )."},{"issue":"4","key":"23_CR18","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M. Yannakakis","year":"1985","unstructured":"M. Yannakakis, \u2018A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees\", J. ACM 32, 4 ( 1985 ), pp. 950\u2013959.","journal-title":"J. ACM"},{"key":"23_CR19","unstructured":"O. Wing, \"Automated Gate Matrix Layout\", Proc. IEEE 1982 Symp. on Circuits and Systems ( 1982 ), pp. 681\u2013685."}],"container-title":["Lecture Notes in Computer Science","VLSI Algorithms and Architectures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16766-8_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:11:09Z","timestamp":1605625869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16766-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167662","9783540387466"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-16766-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}