{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,7]],"date-time":"2024-12-07T05:10:19Z","timestamp":1733548219787,"version":"3.30.1"},"reference-count":16,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2000,3,1]],"date-time":"2000-03-01T00:00:00Z","timestamp":951868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4886,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,3]]},"DOI":"10.1016\/s0304-3975(99)00181-4","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T01:51:05Z","timestamp":1027648265000},"page":"25-42","source":"Crossref","is-referenced-by-count":23,"title":["Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems"],"prefix":"10.1016","volume":"235","author":[{"given":"Avrim","family":"Blum","sequence":"first","affiliation":[]},{"given":"Goran","family":"Konjevod","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]},{"given":"Santosh","family":"Vempala","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(99)00181-4_BIB1","doi-asserted-by":"crossref","unstructured":"A. Blum, G. Konjevod, R. Ravi, S. Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Proc. 30th Annual ACM Symp. on Theory of Computing, 1998, pp. 90\u201399.","DOI":"10.1145\/276698.276717"},{"key":"10.1016\/S0304-3975(99)00181-4_BIB2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1002\/jgt.3190060302","article-title":"The bandwidth problem for graphs and matrices \u2014 a survey","volume":"6","author":"Chinn","year":"1982","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0304-3975(99)00181-4_BIB3","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0012-365X(89)90083-6","article-title":"Graphs with small band- and cutwidth","volume":"75","author":"Chung","year":"1989","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(99)00181-4_BIB4","doi-asserted-by":"crossref","first-page":"109","DOI":"10.21136\/CMJ.1970.100949","article-title":"A remark on a problem of Harary","volume":"20","author":"Chv\u00e1tal","year":"1970","journal-title":"Czechoslovak Math. J."},{"key":"10.1016\/S0304-3975(99)00181-4_BIB5","doi-asserted-by":"crossref","unstructured":"G. Even. J. Naor, S. Rao, B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Proc. 35th Annual Conf. on Foundations of Computer Science, 1996, pp. 62\u201371.","DOI":"10.1109\/SFCS.1995.492463"},{"key":"10.1016\/S0304-3975(99)00181-4_BIB6","doi-asserted-by":"crossref","unstructured":"U. Feige, Approximating the bandwidth via volume respecting embeddings, Proc. 30th Annual ACM Symp. on Theory of Computing, 1998, pp. 90\u201399.","DOI":"10.1145\/276698.276716"},{"key":"10.1016\/S0304-3975(99)00181-4_BIB7","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","article-title":"Complexity results for bandwidth minimization","volume":"34","author":"Garey","year":"1978","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0304-3975(99)00181-4_BIB8","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J. Assoc. Comput. Mach."},{"year":"1983","series-title":"Matrix Computations","author":"Golub","key":"10.1016\/S0304-3975(99)00181-4_BIB9"},{"year":"1988","series-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel","key":"10.1016\/S0304-3975(99)00181-4_BIB10"},{"key":"10.1016\/S0304-3975(99)00181-4_BIB11","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02090396","article-title":"Bandwidth minimization: an approximation algorithm for caterpillars","volume":"24","author":"Haralambides","year":"1991","journal-title":"Math. Systems Theory"},{"key":"10.1016\/S0304-3975(99)00181-4_BIB12","doi-asserted-by":"crossref","unstructured":"T. Kloks, D. Kratsch, H. M\u00fcller, Approximating the bandwidth for asteroidal triple-free graphs, Proc. ESA\u201995, Lecture Notes in Computer Science, vol. 979, Springer, Berllin ,1995. 434\u2013447.","DOI":"10.1007\/3-540-60313-1_161"},{"key":"10.1016\/S0304-3975(99)00181-4_BIB13","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0607057","article-title":"The bandwidth-minimization problem for caterpillars with hairlength 3 is NP-complete","volume":"7","author":"Monien","year":"1986","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"10.1016\/S0304-3975(99)00181-4_BIB14","unstructured":"J. Naor, personal communication, July 1998."},{"key":"10.1016\/S0304-3975(99)00181-4_BIB15","article-title":"Interior-point polynomial algorithms in convex programming","volume":"13","author":"Nesterov","year":"1994","journal-title":"SIAM Stud. Appl. Math."},{"key":"10.1016\/S0304-3975(99)00181-4_BIB16","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02280884","article-title":"The NP-completeness of the bandwidth minimization problem","volume":"16","author":"Papadimitriou","year":"1976","journal-title":"Computing"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001814?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397599001814?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,6]],"date-time":"2024-12-06T11:52:26Z","timestamp":1733485946000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397599001814"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,3]]}},"alternative-id":["S0304397599001814"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(99)00181-4","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2000,3]]}}}