{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:47:58Z","timestamp":1787510878435,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540603139","type":"print"},{"value":"9783540449133","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60313-1_161","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:16:44Z","timestamp":1330262204000},"page":"434-447","source":"Crossref","is-referenced-by-count":27,"title":["Approximating the bandwidth for asteroidal triple-free graphs"],"prefix":"10.1007","author":[{"given":"T.","family":"Kloks","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D.","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"H.","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., D. G. Corneil and A. Proskurowski, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods 8 (1987), pp. 277\u2013284.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"32_CR2","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1137\/0602041","volume":"2","author":"S. F. Assmann","year":"1981","unstructured":"Assmann, S. F., G. W. Peck, M. M. Syslo and J. Zak, The bandwidth of caterpillars with hairs of length 1 and 2, SIAM Journal on Algebraic and Discrete Methods 2 (1981), pp. 387\u2013393.","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"32_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., M. R. Fellows and M. T. Hallet, Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy, Proceedings of the 26th STOC, 1994, pp. 449\u2013458.","DOI":"10.1145\/195058.195229"},{"key":"32_CR4","doi-asserted-by":"crossref","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, N.E. Gibbs, The bandwidth problem for graphs and matrices \u2014 a survey, Journal of Graph Theory 6 (1982), pp. 223\u2013254.","journal-title":"Journal of Graph Theory"},{"key":"32_CR5","doi-asserted-by":"crossref","unstructured":"D.G. Corneil, S. Olariu, and L. Stewart, Asteroidal triple-free graphs, Proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science WG'93, Lecture Notes in Computer Science, Vol. 790, Springer-Verlag, 1994, pp. 211\u2013224.","DOI":"10.1007\/3-540-57899-4_54"},{"key":"32_CR6","unstructured":"Corneil, D. G., S. Olariu and L. Stewart, Linear time algorithms to compute dominating pairs in asteroidal triple-free graphs. To appear in: Proceedings ICALP'95."},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"Dahlhaus, E. and M. Karpinski, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Proceedings of the 30th FOCS, 1989, pp. 454\u2013459.","DOI":"10.1109\/SFCS.1989.63518"},{"key":"32_CR8","doi-asserted-by":"crossref","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":"32_CR9","volume-title":"Algorithmic graph theory and perfect graphs","author":"M. C. Golumbic","year":"1980","unstructured":"Golumbic, M. C., Algorithmic graph theory and perfect graphs, Academic Press, New York, 1980."},{"key":"32_CR10","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1016\/0196-6774(84)90006-3","volume":"5","author":"E. Gurari","year":"1984","unstructured":"Gurari, E. and I. H. Sudborough, Improved dynamic programming algorithms for the bandwidth minimization and the mincut linear arrangement problem, Journal on Algorithms, 5, (1984), pp. 531\u2013546.","journal-title":"Journal on Algorithms"},{"key":"32_CR11","unstructured":"Kaplan, H. and R. Shamir, Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. Manuscript, 1993."},{"key":"32_CR12","doi-asserted-by":"crossref","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":"32_CR13","doi-asserted-by":"crossref","unstructured":"Kloks, T., Treewidth \u2014 Computations and Approximations, Springer-Verlag, Lecture Notes in Computer Science 842, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"32_CR14","volume-title":"Forschungsergebnisse Math\/95\/6","author":"T. Kloks","year":"1995","unstructured":"Kloks, T., D. Kratsch and H. M\u00fcller, Approximating the bandwidth for asteroidal triple-free graphs, Forschungsergebnisse Math\/95\/6, Friedrich-Schiller-Universit\u00e4t Jena, Germany, 1995."},{"key":"32_CR15","volume-title":"Computing Science Notes 93\/46","author":"T. Kloks","year":"1993","unstructured":"Kloks, T., D. Kratsch and J. Spinrad, Treewidth and pathwidth of cocomparability graphs of bounded dimension, Computing Science Notes 93\/46, Eindhoven University of Technology, Eindhoven, The Netherlands, 1993."},{"key":"32_CR16","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0890-5401(91)90045-4","volume":"95","author":"R. Mahesh","year":"1991","unstructured":"Mahesh, R., C. Pandu Rangan and Aravind Srinivasan, On finding the minimum bandwidth of interval graphs, Information and Computation 95 (1991), pp. 218\u2013224.","journal-title":"Information and Computation"},{"key":"32_CR17","unstructured":"M\u00f6hring, R. H., Triangulating graphs without asteroidal triples. Technical Report 365\/1993, Technische Universit\u00e4t Berlin, Fachbereich Mathematik, 1993."},{"key":"32_CR18","doi-asserted-by":"crossref","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":"32_CR19","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1137\/0205012","volume":"5","author":"T. Ohtsuki","year":"1976","unstructured":"Ohtsuki, T., A fast algorithm for finding an optimal ordering for vertex elimination on a graph, SIAM J. Comput. 5 (1976), pp. 133\u2013145.","journal-title":"SIAM J. Comput."},{"key":"32_CR20","doi-asserted-by":"crossref","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":"32_CR21","unstructured":"Parra, A. and P. Scheffler, Treewidth equals bandwidth for AT-free claw-free graphs. Technical Report 436\/1995, Technische Universit\u00e4t Berlin, Fachbereich Mathematik, 1995."},{"key":"32_CR22","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), 177\u2013187.","journal-title":"Discrete Mathematics"},{"key":"32_CR23","first-page":"139","volume-title":"Proof techniques in graph theory","author":"F. S. Roberts","year":"1969","unstructured":"Roberts, F. S., Indifference graphs, In: Proof techniques in graph theory, (F. Harary, ed.), pp. 139\u2013146. Academic Press, New York, (1969)."},{"key":"32_CR24","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. J. Rose","year":"1976","unstructured":"Rose, D. J., R. E. Tarjan and G. Lueker, Algorithmic aspects of vertex elimination of graphs, SIAM J. Comput. 5 (1976), pp. 266\u2013283.","journal-title":"SIAM J. Comput."},{"key":"32_CR25","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/0214048","volume":"14","author":"J. Spinrad","year":"1985","unstructured":"Spinrad, J., On comparability and permutation graphs, SIAM J. on Comput. 14 (1985), pp. 658\u2013670.","journal-title":"SIAM J. on Comput."},{"key":"32_CR26","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":"32_CR27","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1137\/0215041","volume":"15","author":"J. S. Turner","year":"1986","unstructured":"Turner, J. S., On the probable performance of heuristics for bandwidth minimization, SIAM J. Comput., 15, (1986), pp. 561\u2013580.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60313-1_161.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:58:08Z","timestamp":1605628688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60313-1_161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540603139","9783540449133"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-60313-1_161","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}