{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:30:24Z","timestamp":1725507024497},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540787723"},{"type":"electronic","value":"9783540787730"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-78773-0_19","type":"book-chapter","created":{"date-parts":[[2008,4,3]],"date-time":"2008-04-03T08:38:35Z","timestamp":1207211915000},"page":"216-227","source":"Crossref","is-referenced-by-count":2,"title":["Bandwidth of Bipartite Permutation Graphs in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Pinar","family":"Heggernes","sequence":"first","affiliation":[]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Meister","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1137\/0602041","volume":"2","author":"S.F. Assmann","year":"1981","unstructured":"Assmann, S.F., Peck, G.W., Sys\u0142o, M.M., Zak, J.: The bandwidth of caterpillars with hairs of length 1 and 2. SIAM J. Algebraic and Discrete Methods\u00a02, 387\u2013393 (1981)","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"19_CR2","unstructured":"Blache, G., Karpinski, M., Wirtgen, J.: On approximation intractability of the bandwidth problem. Technical report, University of Bonn (1997)"},{"key":"19_CR3","first-page":"100","volume-title":"Proceedings of STOC 1998","author":"A. Blum","year":"1998","unstructured":"Blum, A., Konjevod, G., Ravi, R., Vempala, S.: Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. In: Proceedings of STOC 1998, pp. 100\u2013105. ACM, New York (1998)"},{"key":"19_CR4","first-page":"449","volume-title":"Proceedings of STOC 1994","author":"H.L. Bodlaender","year":"1994","unstructured":"Bodlaender, H.L., Fellows, M.R., Hallet, M.T.: Beyond NP-completeness for problems of bounded width (extended abstract): hardness for the W hierarchy. In: Proceedings of STOC 1994, pp. 449\u2013458. ACM, New York (1994)"},{"key":"19_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"19_CR6","first-page":"90","volume-title":"Proceedings of STOC 1998","author":"U. Feige","year":"1998","unstructured":"Feige, U.: Approximating the Bandwidth via Volume Respecting Embeddings. In: Proceedings of STOC 1998, pp. 90\u201399. ACM, New York (1998)"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/11538462_6","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"U. Feige","year":"2005","unstructured":"Feige, U., Talwar, K.: Approximating the Bandwidth of Caterpillars. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 62\u201373. Springer, Heidelberg (2005)"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1023\/A:1012267732204","volume":"18","author":"P. Fishburn","year":"2001","unstructured":"Fishburn, P., Tanenbaum, P., Trenk, A.: Linear discrepancy and bandwidth. Order\u00a018, 237\u2013245 (2001)","journal-title":"Order"},{"key":"19_CR9","volume-title":"Computer Solution of Large Sparse Positive Definite Systems","author":"J.A. George","year":"1981","unstructured":"George, J.A., Liu, J.W.H.: Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall Inc., Englewood Cliffs, New Jersey (1981)"},{"key":"19_CR10","unstructured":"Gupta, A.: Improved bandwidth approximation for trees. In: Proceedings of SODA 2000, pp. 788\u2013793. ACM, SIAM (2000)"},{"issue":"3","key":"19_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02090396","volume":"24","author":"J. Haralambides","year":"1991","unstructured":"Haralambides, J., Makedon, F., Monien, B.: Bandwidth Minimization: An Approximation Algorithm for Caterpillars. Mathematical Systems Theory\u00a024(3), 169\u2013177 (1991)","journal-title":"Mathematical Systems Theory"},{"key":"19_CR12","unstructured":"Heggernes, P., Kratsch, D., Meister, D.: Bandwidth of bipartite permutation graphs in polynomial time. In: Reports in Informatics, University of Bergen, Norway, vol.\u00a0356 (2007)"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0403033","volume":"3","author":"D.J. Kleitman","year":"1990","unstructured":"Kleitman, D.J., Vohra, R.V.: Computing the bandwidth of interval graphs. SIAM J. Disc. Math.\u00a03, 373\u2013375 (1990)","journal-title":"SIAM J. Disc. Math."},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/S0020-0190(98)00173-2","volume":"68","author":"T. Kloks","year":"1998","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Bandwidth of chain graphs. Information Processing Letters\u00a068, 313\u2013315 (1998)","journal-title":"Information Processing Letters"},{"key":"19_CR15","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1006\/jagm.1998.0997","volume":"32","author":"T. Kloks","year":"1999","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Approximating the bandwidth for AT-free graphs. Journal of Algorithms\u00a032, 41\u201357 (1999)","journal-title":"Journal of Algorithms"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/j.dam.2004.10.001","volume":"146","author":"D. Meister","year":"2005","unstructured":"Meister, D.: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs. Disc. Appl. Math.\u00a0146, 193\u2013218 (2005)","journal-title":"Disc. Appl. Math."},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0607057","volume":"7","author":"B. Monien","year":"1986","unstructured":"Monien, B.: The bandwidth minimization problem with hair length 3 is NP-complete. SIAM J. Alg. Disc. Meth.\u00a07, 505\u2013512 (1986)","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"19_CR18","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"C. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.: The NP-completeness of the bandwidth minimization problem. Computing\u00a016, 263\u2013270 (1976)","journal-title":"Computing"},{"key":"19_CR19","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. Disc. Appl. Math.\u00a018, 279\u2013292 (1987)","journal-title":"Disc. Appl. Math."},{"key":"19_CR20","first-page":"82","volume-title":"Proceedings of FOCS 1998","author":"W. Unger","year":"1998","unstructured":"Unger, W.: The Complexity of the Approximation of the Bandwidth Problem. In: Proceedings of FOCS 1998, pp. 82\u201391. IEEE, Los Alamitos (1998)"},{"key":"19_CR21","first-page":"31","volume":"13","author":"J.H. Yan","year":"1997","unstructured":"Yan, J.H.: The bandwidth problem in cographs. Tamsui Oxf. J. Math. Sci.\u00a013, 31\u201336 (1997)","journal-title":"Tamsui Oxf. J. Math. Sci."}],"container-title":["Lecture Notes in Computer Science","LATIN 2008: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-78773-0_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:21:32Z","timestamp":1619522492000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-78773-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540787723","9783540787730"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-78773-0_19","relation":{},"subject":[]}}