{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T14:14:53Z","timestamp":1778249693086,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602163","type":"print"},{"value":"9783540447337","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0030846","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T03:51:40Z","timestamp":1133409100000},"page":"313-323","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient parallel algorithms for some tree layout problems"],"prefix":"10.1007","author":[{"given":"J.","family":"D\u00edaz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A.","family":"Gibbons","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Pantziou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Serna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Toran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"33_CR1","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0196-6774(89)90017-5","volume":"10","author":"K. Abrahamson","year":"1989","unstructured":"K. Abrahamson, N. Dadoun, D. Kirkpatrick, and K. Przytycka. A simple parallel tree contraction algorithm. Journal of Algorithms, 10:287\u2013302, 1989.","journal-title":"Journal of Algorithms"},{"issue":"3","key":"33_CR2","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/0125042","volume":"25","author":"D. Adolphson","year":"1973","unstructured":"D. Adolphson and T.C. Hu. Optimal linear ordering. SIAM J. on Applied Mathematics, 25(3):403\u2013423, Nov 1973.","journal-title":"SIAM J. on Applied Mathematics"},{"key":"33_CR3","first-page":"262","volume":"23","author":"M. Chung","year":"1982","unstructured":"M. Chung, F. Makedon, I.H. Sudborough, and J. Turner. Polynomial time algorithms for the min cut problem on degree restricted trees. In FOCS, volume 23, pages 262\u2013271, Chicago, Nov 1982.","journal-title":"FOCS"},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"J. D\u00edaz. Graph layout problems. In I.M. Havel and V. Koubek, editors, Mathematical Foundations of Computer Science, volume 629, pages 14\u201324. Springer-Verlag, Lecture Notes in Computer Science, 1992.","DOI":"10.1007\/3-540-55808-X_2"},{"key":"33_CR5","volume-title":"Technical report, TR-43","author":"S. Even","year":"1978","unstructured":"S. Even and Y. Shiloach. NP-completeness of several arrangements problems. Technical report, TR-43 The Technical, Haifa, 1978."},{"key":"33_CR6","first-page":"91","volume-title":"Proc. 11th. Conf. on Information Sciences and Systems","author":"F. Gavril","year":"1977","unstructured":"F. Gavril. Some NP-complete problems on graphs. In Proc. 11th. Conf. on Information Sciences and Systems, pages 91\u201395, John Hopkins Univ., Baltimore, 1977."},{"key":"33_CR7","volume-title":"Computers and Intractability: A Guide to Oie Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to Oie Theory of NP-Completeness. Freeman, San Francisco, 1979."},{"issue":"3","key":"33_CR8","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/S0021-9800(66)80059-5","volume":"1","author":"L.H. Harper","year":"1966","unstructured":"L.H. Harper. Optimal numberings and isoperimetric problems on graphs. Journal of Combinatorial Theory, 1(3):385\u2013393, 1966.","journal-title":"Journal of Combinatorial Theory"},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"B. Monien and I.H. Sudborough. Min cut is NP-complete for edge weighted trees. In L. Kott, editor, Proc. 13th. Coll. on Automata, Languages and Programming, pages 265\u2013274. Springer-Verlag, Lectures Notes in Computer Science, 1986.","DOI":"10.1007\/3-540-16761-7_76"},{"key":"33_CR10","first-page":"267","volume-title":"Layout design and verification","author":"M.T. Shing","year":"1986","unstructured":"M.T. Shing and T. C. Hu. Computational complexity of layout problems. In T. Ohtsuki, editor, Layout design and verification, pages 267\u2013294, Amsterdam, 1986. North-Holland."},{"issue":"1","key":"33_CR11","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1137\/0208002","volume":"8","author":"Y. Shiloach","year":"1979","unstructured":"Yossi Shiloach. A minimum linear arrangement algorithm for undirected trees. SIAM J. on Computing, 8(1):15\u201331, February 1979.","journal-title":"SIAM J. on Computing"},{"key":"33_CR12","first-page":"274","volume":"24","author":"M. Yannakakis","year":"1983","unstructured":"Mihalis Yannakakis. A polynomial algorithm for the min cut linear arrangement of trees. In IEEE Symp. on Found. of Comp. Sci., volume 24, pages 274\u2013281, Providence RI, Nov. 1983.","journal-title":"IEEE Symp. on Found. of Comp. Sci."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0030846","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T13:41:23Z","timestamp":1778247683000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0030846"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602163","9783540447337"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/bfb0030846","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"20 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}