Laying Out Sparse Graphs with Provably Minimum Bandwidth

References

• Blum A., Konjevod G., Ravi R., Vempala S. Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Theoret. Comput. Sci. (2000) 235:25–42Crossref, Google Scholar
• Boisvert R., Pozo R., Remington K., Barrett R., Dongarra J., Boisvert R. Matrix market: A web resource for test matrix collections. The Quality of Numerical Software: Assessment and Enhancement (1997) (Chapman and Hall, London) Crossref, Google Scholar
• Chinn P., Chvátalova J., Dewdney A., Gibbs N. The bandwidth problem for graph and matrices—A survey. J. Graph Theory (1982) 6:223–254Crossref, Google Scholar
• Chung F. R. K., Seymour P. D. Graphs with small bandwidth and cutwidth. Discrete Math. (1989) 75:113–119Crossref, Google Scholar
• Chvátal V. A remark on a problem of Harary. Czechoslovak Math. J. (1970) 20:95Crossref, Google Scholar
• Cuthill E., McKee J. Reducing the bandwidth of sparse symmetric matrices. ACM National Conf. Proc. (1969) 24:157–172Google Scholar
• Del Corso G. M., Manzini G. Finding exact solutions to the bandwidth minimization problem. Computing (1999) 62:189–203Crossref, Google Scholar
• Del Corso G. M., Romani F. Heuristic spectral techniques for the reduction of bandwidth and work-bound of sparse matrices. Numer. Algorithms (2001) 28:117–136Crossref, Google Scholar
• Dueck G. W., Jeffs J. A heuristic bandwidth reduction algorithm. J. Combin. Math. Combin. Comput. (1995) 18:97–108Google Scholar
• Esposito A., Catalano M. S. F., Malucelli F., Tarricone L. A new matrix bandwidth reduction algorithm. Oper. Res. Lett. (1999) 23:99–107Crossref, Google Scholar
• Feige U. Approximating the bandwidth via volume respecting embeddings. J. Comput. System Sci. (2000) 60:510–539Crossref, Google Scholar
• Garey M. R., Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (Freeman, New York) Google Scholar
• Garey M. R., Graham R. L., Johnson D. S., Knuth D. E. Complexity results for bandwidth minimization. SIAM J. Appl. Math. (1978) 34:477–495Crossref, Google Scholar
• Gibbs N. E., Poole W. G., Stockmeier P. K. An algorithm for reducing the bandwidth and profile of sparse matrices. SIAM J. Numer. Anal. (1976a) 13:236–250Crossref, Google Scholar
• Gibbs N. E., Poole W. G., Stockmeier P. K. A comparison of several bandwidth and profile reduction algorithms. ACM Trans. Math. Software (1976b) 2:322–330Crossref, Google Scholar
• Gurari E. M., Sudborough I. H. Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem. J. Algorithms (1984) 5:531–546Crossref, Google Scholar
• Johnson D. S., Trick M. A.Cliques, Coloring and Satisfiability: Second DIMACS Implementation Challenge (1996) 26(AMS Press, Providence, RI) DIMACS Series in Discrete Mathematics and Theoretical Computer ScienceCrossref, Google Scholar
• Martí R., Laguna M., Glover F., Campos V. Reducing the bandwidth of a sparse matrix with tabu search. Eur. J. Oper. Res. (2001) 135:450–459Crossref, Google Scholar
• Turner J. S. On the probable performance of heuristics for bandwidth minimization. SIAM J. Comput. (1986) 15:561–580Crossref, Google Scholar
• Unger W. The complexity of the approximation of the bandwidth problem. Proc. 39th IEEE Sympos. Foundations Comput. Sci. (1998) (IEEE Computer Society Press, New York) 82–91Crossref, Google Scholar