{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,9]],"date-time":"2026-05-09T03:13:54Z","timestamp":1778296434972,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540167617","type":"print"},{"value":"9783540398592","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_76","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:51:47Z","timestamp":1330195907000},"page":"265-274","source":"Crossref","is-referenced-by-count":11,"title":["Min Cut is NP-complete for edge weighted trees"],"prefix":"10.1007","author":[{"given":"B.","family":"Monien","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,5,31]]},"reference":[{"key":"28_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":"1","key":"28_CR2","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":"28_CR3","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0022-0000(76)80048-7","volume":"13","author":"S. A. Cook","year":"1976","unstructured":"S. A. Cook and R. Sethi, \"Storage Requirements for Deterministic Polynomial Time Recognizable Languages\", J. Comput. Syst. Sci. 13 (1976), pp. 25\u201337.","journal-title":"J. Comput. Syst. Sci."},{"key":"28_CR4","unstructured":"J.A. Ellis, I.H. Sudborough, and J.S. Turner, \"Graph Separation and Search Number\", Proc. 1983 Allerton Conf. on Communication, Control, and Computing."},{"key":"28_CR5","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","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)"},{"key":"28_CR6","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M. R. Garey","year":"1978","unstructured":"Garey, M. R, Graham, R. L, Johnson, D. S and Knuth, D. E, \"Complexity Results for Bandwidth Minimization\", SIAM J. Applied Math. 34 (1978), pp. 477\u2013495.","journal-title":"SIAM J. Applied Math."},{"issue":"3","key":"28_CR7","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/0209038","volume":"9","author":"J. R. Gilbert","year":"1980","unstructured":"Gilbert, J. R, Lengauer, T and Tarjan, R. E, \"The Pebbling Problem is Complete in Polynomial Space\", SIAM Journal on Computing 9,3 1980 pp. 513\u2013524","journal-title":"SIAM Journal on Computing"},{"key":"28_CR8","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J. E. Hopcroft","year":"1977","unstructured":"Hopcroft, J. E, Paul, W and Valiant, L, \"On Time Versus Space\", Journal ACM, 24, (1977), pp. 332\u2013337","journal-title":"Journal ACM"},{"key":"28_CR9","series-title":"Technical Report","volume-title":"Searching and Pebbling","author":"M. Kirousis","year":"1983","unstructured":"M. Kirousis and C. H. Papadimitriou, \"Searching and Pebbling\", Technical Report, National Technical University, Athens, Greece (1983)."},{"key":"28_CR10","unstructured":"S. LaPaugh, \"Recontamination does not Help to Search a Graph\", Technical Report, Electrical Engineering and Computer Science Department, Princeton University (1983)"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"T. Lengauer, \"Black-White Pebbles and Graph Separation\", SIAM J. Algebraic and Discrete Methods, 1982.","DOI":"10.1007\/BF00264496"},{"issue":"2","key":"28_CR12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton and R. E. Tarjan, \"A Separator Theorem for Planar Graphs\", SIAM J. Appl. Math. 36,2 (1979), pp. 177\u2013189","journal-title":"SIAM J. Appl. Math."},{"key":"28_CR13","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0304-3975(81)80004-7","volume":"13","author":"F. M. Heide auf der","year":"1981","unstructured":"F. Meyer auf der Heide, \"A Comparison of Two Variations of a Pebble Game on Graphs\", Theoretical Computer Science 13 (1981), pp. 315\u2013322.","journal-title":"Theoretical Computer Science"},{"key":"28_CR14","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":"28_CR15","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":"28_CR16","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 Foundations of Computer Science Symp. (1981), pp. 376\u2013385"},{"key":"28_CR17","unstructured":"B. Monien, personal communication."},{"key":"28_CR18","first-page":"426","volume-title":"Theory and Application of Graphs","author":"T. D. Parsons","year":"1976","unstructured":"T. D. Parsons, \"Pursuit-Evasion in a Graph\", in Theory and Application of Graphs, Y. Alavi and D. R. Lick, (eds) Springer-Verlag, Berlin, 1976, pp. 426\u2013441"},{"key":"28_CR19","first-page":"549","volume-title":"The Search Number of a Connected Graph","author":"T. D. Parsons","year":"1978","unstructured":"T. D. Parsons, \"The Search Number of a Connected Graph\", Proc. 9th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing, Winnipeg, (1978), pp. 549\u2013554"},{"key":"28_CR20","doi-asserted-by":"crossref","unstructured":"R. Wilber, \"White Pebbles Help\", Proc. 17th Annual ACM Symposium on Theory of Computing, 1985, pp. 103\u2013112.","DOI":"10.1145\/22145.22157"},{"issue":"4","key":"28_CR21","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M. Yannakais","year":"1985","unstructured":"M. Yannakais, \"A Polynomial Algorithm for the Min Cut Linear Arrangement of Trees\", J. ACM 32,4 (1985), pp. 950\u2013959.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16761-7_76.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:10:56Z","timestamp":1605643856000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_76","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}