{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:07Z","timestamp":1725488947969},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540411833"},{"type":"electronic","value":"9783540400646"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40064-8_23","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T04:25:42Z","timestamp":1186892742000},"page":"243-254","source":"Crossref","is-referenced-by-count":7,"title":["Bandwidth of Split and Circular Permutation Graphs"],"prefix":"10.1007","author":[{"given":"Ton","family":"Kloks","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yvan","family":"Le Borgne","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,7,18]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1137\/0602041","volume":"2","author":"S. F. Assmann","year":"1981","unstructured":"Assmann, S. F., G. W. Peck, M. M. Sys lo and J. Zak, The bandwidth of caterpillars with hairs of length 1 and 2, SIAM J. Algebraic Discrete Methods 2 (1981), pp. 387\u2013393.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Blum, A., G. Konjevod, R. Ravi and S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (Dallas, TX, 1998), pp. 111\u2013105.","DOI":"10.1145\/276698.276717"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/jgt.3190060302","volume":"6","author":"P. Z. Chinn","year":"1982","unstructured":"Chinn, P. Z., J. Chv\u00e1talov\u00e1, A. K. Dewdney and N. E. Gibbs, The bandwidthproblem for graphs and matrices-a survey, Journal of Graph Theory 6(1982), pp. 223\u2013254.","journal-title":"Journal of Graph Theory"},{"key":"23_CR4","first-page":"151","volume":"3","author":"F. R. K. Chung","year":"1988","unstructured":"Chung, F. R. K., Labelings of graphs, Selected topics in graph theory 3 (1988), pp. 151\u2013168.","journal-title":"Selected topics in graph theory"},{"key":"23_CR5","volume-title":"Parameterized complexity","author":"R. G. Downey","year":"1998","unstructured":"Downey, R. G. and M. R. Fellows, Parameterized complexity, Springer-Verlag New York, 1998."},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Feige, U., Approximating the bandwidth via volume respecting embeddings, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing(Dallas, TX, 1998).","DOI":"10.1145\/276698.276716"},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M. R. Garey","year":"1978","unstructured":"Garey, M. R., R. L. Graham, D. S. Johnson and D. E. Knuth, Complexity results for bandwidth minimization, SIAM Journal on Applied Mathematics 34 (1978), pp. 477\u2013495.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"23_CR8","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1016\/0196-6774(84)90006-3","volume":"5","author":"E. M. Gurari","year":"1984","unstructured":"Gurari, E. M. and I. H. Sudborough, Improved dynamic programming algorithms for bandwidth minimization and the MinCut linear arrangement problem, J. Algorithms 5 (1984), pp. 531\u2013546.","journal-title":"J. Algorithms"},{"key":"23_CR9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02679454","volume":"30","author":"J. Haralambides","year":"1997","unstructured":"Haralambides, J. and F. Makedon, Approximation algorithms for the bandwidth minimization problem for a large class of trees, Theory Comput. Syst. 30 (1997), pp. 67\u201390.","journal-title":"Theory Comput. Syst."},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02090396","volume":"24","author":"J. Haralambides","year":"1991","unstructured":"Haralambides, J., F. Makedon and F. and B. Monien, Bandwidth minimization: An approximation algorithm for caterpillars, Math. Syst. Theory 24 (1991), pp. 169\u2013177.","journal-title":"Math. Syst. Theory"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1137\/0403033","volume":"3","author":"D. J. Kleitman","year":"1990","unstructured":"Kleitman, D. J. and R.V. Vohra, Computing the bandwidth of interval graphs, SIAM Journal on Discrete Mathematics 3 (1990), pp. 373\u2013375.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"23_CR12","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0012-365X(94)90118-X","volume":"128","author":"D. Kratsch","year":"1994","unstructured":"Kratsch, D., P. Damaschke and A. Lubiw, Dominating cliques in chordal graphs, Discrete Mathematics 128 (1994), pp. 269\u2013276.","journal-title":"Discrete Mathematics"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1006\/jagm.1998.0997","volume":"32","author":"T. Kloks","year":"1999","unstructured":"Kloks, T., D. Kratsch and H. M\u00fcller, Approximating the bandwidth for asteroidal triple-free graphs, Journal of Algorithms 32 (1999), pp. 41\u201357.","journal-title":"Journal of Algorithms"},{"key":"23_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., D. Kratsch, and H. M\u00fcller, Bandwidth of chain graphs, Information Processing Letters 68 (1998), pp. 313\u2013315.","journal-title":"Information Processing Letters"},{"key":"23_CR15","series-title":"Lect Notes Comput Sci","first-page":"248","volume-title":"Approximating bandwidth by mixing layouts of interval graphs","author":"D. Kratsch","year":"2000","unstructured":"Kratsch, D. and L. Stewart, Approximating bandwidth by mixing layouts of interval graphs, Proceedings of STACS\u201999, LNCS 1563, pp. 248\u2013258."},{"key":"23_CR16","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 for caterpillars with hair length 3 is NP-complete, SIAM Journal on Algebraic and Discrete Methods 7 (1986), pp. 505\u2013512.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"23_CR17","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1002\/net.3230120407","volume":"12","author":"D. Rotem","year":"1982","unstructured":"Rotem, D. and J. Urrutia, Circular permutation graphs, Networks 12 (1982), pp. 429\u2013437.","journal-title":"Networks"},{"key":"23_CR18","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"C. H. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C. H., The NP-completeness of the bandwidth minimization problem, Computing 16 (1976), pp. 263\u2013270.","journal-title":"Computing"},{"key":"23_CR19","unstructured":"Parra, A., structural and algorithmic aspects of chordal graph embeddings, PhD-thesis, Technische Universit\u00e4t Berlin, 1996."},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0012-365X(92)90268-K","volume":"103","author":"G. W. Peck","year":"1992","unstructured":"Peck, G. W. and Aditya Shastri, Bandwidth of theta graphs with short paths, Discrete Mathematics 103 (1992), pp. 177\u2013187.","journal-title":"Discrete Mathematics"},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1137\/S0895480192232333","volume":"7","author":"A. P. Sprague","year":"1994","unstructured":"Sprague, A. P., An O(n log n) algorithm for bandwidth of interval graphs, SIAM Journal on Discrete Mathematics 7 (1994), pp. 213\u2013220.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Unger, W., The complexity of the approximation of the bandwidth problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science (Palo Alto, California, 1998), pp. 82\u201391.","DOI":"10.1109\/SFCS.1998.743431"},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/inco.1997.2641","volume":"136","author":"G. Venkatesan","year":"1997","unstructured":"Venkatesan, G., U. Rotics, M. S. Madanlal, J. A. Makowsky, and C. Pandu Rangan, Restrictions of minimum spanner problems, Information and Computation 136 (1997), pp. 143\u2013164.","journal-title":"Information and Computation"}],"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\/3-540-40064-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T23:39:56Z","timestamp":1556753996000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40064-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540411833","9783540400646"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-40064-8_23","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}