{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:55:38Z","timestamp":1725569738848},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642169250"},{"type":"electronic","value":"9783642169267"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16926-7_9","type":"book-chapter","created":{"date-parts":[[2010,11,10]],"date-time":"2010-11-10T02:48:26Z","timestamp":1289357306000},"page":"75-87","source":"Crossref","is-referenced-by-count":4,"title":["Computing the Cutwidth of Bipartite Permutation Graphs in Linear Time"],"prefix":"10.1007","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[]},{"given":"Pim","family":"van \u2019t Hof","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/0125042","volume":"25","author":"D. Adolphson","year":"1973","unstructured":"Adolphson, D., Hu, T.C.: Optimal linear ordering. SIAM J. Appl. Math.\u00a025, 403\u2013423 (1973)","journal-title":"SIAM J. Appl. Math."},{"key":"9_CR2","first-page":"21","volume-title":"Proceedings of FOCS 1996","author":"S. Arora","year":"1996","unstructured":"Arora, S., Frieze, A., Kaplan, H.: A new rounding procedure for the assignment problem with applications to dense graphs arrangements. In: Proceedings of FOCS 1996, pp. 21\u201330. IEEE, Los Alamitos (1996)"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/11604686_24","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"G. Blin","year":"2005","unstructured":"Blin, G., Fertin, G., Hermelin, D., Vialette, S.: Fixed-parameter algorithms for protein similarity search under RNA structure constraints. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 271\u2013282. Springer, Heidelberg (2005)"},{"key":"9_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.: Graph Classes: A Survey. SIAM, Philadelphia (1999)"},{"key":"9_CR5","first-page":"273","volume":"67","author":"A. Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Combinatorica\u00a067, 273\u2013289 (2003)","journal-title":"Ars Combinatorica"},{"key":"9_CR6","first-page":"262","volume-title":"Proceedings of FOCS 1982","author":"M.J. Chung","year":"1982","unstructured":"Chung, M.J., Makedon, F., Sudborough, I.H., Turner, J.: Polynomial time algorithms for the min cut problem on degree restricted d trees. In: Proceedings of FOCS 1982, pp. 262\u2013271. IEEE, Los Alamitos (1982)"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/jagm.2000.1149","volume":"39","author":"J. D\u00edaz","year":"2001","unstructured":"D\u00edaz, J., Penrose, M., Petit, J., Serna, M.J.: Approximating layout problems on random geometric graphs. Journal of Algorithms\u00a039, 78\u2013117 (2001)","journal-title":"Journal of Algorithms"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J. D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.J.: A survey of graph layout problems. ACM Computing Surveys\u00a034, 313\u2013356 (2002)","journal-title":"ACM Computing Surveys"},{"key":"9_CR9","first-page":"91","volume-title":"11th Conference on Information Sciences and Systems","author":"F. Gavril","year":"1977","unstructured":"Gavril, F.: Some NP-complete problems on graphs. In: 11th Conference on Information Sciences and Systems, pp. 91\u201395. John Hopkins University, Baltimore (1977)"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/978-3-540-92248-3_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P. Heggernes","year":"2008","unstructured":"Heggernes, P., Lokshtanov, D., Mihai, R., Papadopoulos, C.: Cutwidth of split graphs, threshold graphs, and proper interval graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 218\u2013229. Springer, Heidelberg (2008)"},{"key":"9_CR11","first-page":"225","volume-title":"Handbook on Operations Research and Management Sciences","author":"M. J\u00fcnger","year":"1995","unstructured":"J\u00fcnger, M., Reinelt, G., Rinaldi, G.: The traveling salesman problem. In: Handbook on Operations Research and Management Sciences, vol.\u00a07, pp. 225\u2013330. North-Holland, Amsterdam (1995)"},{"key":"9_CR12","first-page":"11","volume-title":"Proceedings of STOC 1996","author":"D.R. Karger","year":"1996","unstructured":"Karger, D.R.: A randomized fully polynomial approximation scheme for the all terminal network reliability problem. In: Proceedings of STOC 1996, pp. 11\u201317. ACM, New York (1996)"},{"key":"9_CR13","first-page":"422","volume-title":"Proceedings of FOCS 1988","author":"F.T. Leighton","year":"1988","unstructured":"Leighton, F.T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proceedings of FOCS 1988, pp. 422\u2013431. IEEE, Los Alamitos (1988)"},{"key":"9_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/BFb0036931","volume-title":"Automata, Languages and Programming","author":"F. Makedon","year":"1983","unstructured":"Makedon, F., Sudborough, I.H.: Minimizing width in linear layouts. In: D\u00edaz, J. (ed.) ICALP 1983. LNCS, vol.\u00a0154, pp. 478\u2013490. Springer, Heidelberg (1983)"},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/3-540-16761-7_76","volume-title":"Automata, Languages and Programming","author":"B. Monien","year":"1986","unstructured":"Monien, B., Sudborough, I.H.: Min cut is NP-complete for edge weighted trees. In: Kott, L. (ed.) ICALP 1986. LNCS, vol.\u00a0226, pp. 265\u2013274. Springer, Heidelberg (1986)"},{"key":"9_CR16","series-title":"Lecture Notes in Computer Science","first-page":"497","volume-title":"Algorithms - ESA \u201995","author":"P. Mutzel","year":"1995","unstructured":"Mutzel, P.: A polyhedral approach to planar augmentation and related problems. In: Spirakis, P.G. (ed.) ESA 1995. LNCS, vol.\u00a0979, pp. 497\u2013507. Springer, Heidelberg (1995)"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J. Spinrad","year":"1987","unstructured":"Spinrad, J., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discrete Applied Mathematics\u00a018, 279\u2013292 (1987)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jalgor.2004.12.001","volume":"56","author":"D.M. Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth I: A linear time fixed parameter algorithm. Journal of Algorithms\u00a056, 1\u201324 (2005)","journal-title":"Journal of Algorithms"},{"key":"9_CR19","first-page":"24","volume":"56","author":"D.M. Thilikos","year":"2005","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Cutwidth II: Algorithms for partial w-trees of bounded degree. Journal of Algorithms\u00a056, 24\u201349 (2005)","journal-title":"Journal of Algorithms"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M. Yannakakis","year":"1985","unstructured":"Yannakakis, M.: A polynomial algorithm for the min cut linear arrangement of trees. Journal of ACM\u00a032, 950\u2013988 (1985)","journal-title":"Journal of ACM"},{"key":"9_CR21","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF02662875","volume":"10","author":"J. Yuan","year":"1995","unstructured":"Yuan, J., Zhou, S.: Optimal labelling of unit interval graphs. Appl. Math. J. Chinese Univ. Ser.\u00a0B (English edition)\u00a010, 337\u2013344 (1995)","journal-title":"Appl. Math. J. Chinese Univ. Ser.\u00a0B (English edition)"}],"container-title":["Lecture Notes in Computer Science","Graph Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16926-7_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,22]],"date-time":"2019-03-22T00:59:04Z","timestamp":1553216344000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16926-7_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642169250","9783642169267"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16926-7_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}