Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- 1 March 2000
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 235 (1) , 25-42
- https://doi.org/10.1016/s0304-3975(99)00181-4
Abstract
No abstract availableKeywords
This publication has 12 references indexed in Scilit:
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problemsPublished by Association for Computing Machinery (ACM) ,1998
- Approximating the bandwidth via volume respecting embeddings (extended abstract)Published by Association for Computing Machinery (ACM) ,1998
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Approximating the bandwidth for asteroidal triple-free graphsPublished by Springer Nature ,1995
- Bandwidth Minimization: An approximation algorithm for caterpillarsTheory of Computing Systems, 1991
- Graphs with small bandwidth and cutwidthDiscrete Mathematics, 1989
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-CompleteSIAM Journal on Algebraic Discrete Methods, 1986
- The bandwidth problem for graphs and matrices—a surveyJournal of Graph Theory, 1982
- Complexity Results for Bandwidth MinimizationSIAM Journal on Applied Mathematics, 1978
- The NP-Completeness of the bandwidth minimization problemComputing, 1976