On Bounding the Bandwidth of Graphs with Symmetry

References

• Balogh J, Bezrukov SL, Harper LH, Seress A (2008) On the bandwidth of 3-dimensional Hamming graphs. Theoret. Comput. Sci. 407(1–3): 488–495.Crossref, Google Scholar
• Berger-Wolf TY, Reingold EM (2002) Index assignment for multichannel communication under failure. IEEE Trans. Inform. Theory 48(10):2656–2668.Crossref, Google Scholar
• Blum A, Konjevod G, Ravi R, Vempala S (2000) Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Theoret. Comput. Sci. 235(1):25–42.Crossref, Google Scholar
• Cameron PJ (1999) Permutation Groups (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Chinn PZ, Chvátalová J, Dewdney AK, Gibbs NE (1982) The bandwidth problem for graphs and matrices—A survey. J. Graph Theory 6(3):223–254.Crossref, Google Scholar
• Chvátal V (1970) A remark on a problem of Harary. Czechoslovak Math. J. 20(1):109–111.Crossref, Google Scholar
• Chvátalová J (1975) Optimal labelling of a product of two paths. Discrete Math. 11:249–253.Crossref, Google Scholar
• Cuthill E, McKee J (1996) Reducing the bandwidth of sparse symmetric matrices. ACM ’69 Proc. 24th Nat. Conf. (ACM, New York), 157–172.Google Scholar
• De Klerk E, Sotirov R (2010) Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. Ser. A 122(2):225–246.Crossref, Google Scholar
• De Klerk E, Sotirov R (2012) Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Program. Ser. A 133(1):75–91.Crossref, Google Scholar
• De Klerk E, de Oliveira Filho FM, Pasechnik DV (2012) Relaxations of combinatorial problems via association schemes. Anjos MF, Lasserre JB, eds. Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, Internat. Ser. ORMS, Vol. 166 (Springer, New York), 171–200.Crossref, Google Scholar
• De Klerk E, Nagy M, Sotirov R (2013) On semidefinite programming bounds for graph bandwidth. Optim. Methods Softw. 28(3): 485–500.Crossref, Google Scholar
• De Klerk E, Pasechnik DV, Sotirov R, Dobre C (2012) On semidefinite programming relaxations of maximum k-section. Math. Program. Ser. B 136(2):253–278.Crossref, Google Scholar
• Díaz J, Petit J, Serna M (2002) A survey on graph layout problems. ACM Comput. Surveys 34(3):313–356.Crossref, Google Scholar
• Dunagan J, Vempala S (2001) On Euclidean embeddings and bandwidth minimization. Goemans M, Jansen K, Rolim J, Trevisan L, eds. Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques. Lecture Notes in Computer Science, Vol. 2129 (Springer, Berlin), 229–240.Crossref, Google Scholar
• GAP Group, The (2012) GAP—Groups, algorithms, and programming. Version 4.5.6. http://www.gap-system.org.Google Scholar
• Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, San Francisco).Google Scholar
• Garey MR, Graham RL, Johnson DS, Knuth DE (1978) Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34(3): 477–495.Crossref, Google Scholar
• Graham A (1981) Kronecker Products and Matrix Calculus with Applications (Ellis Horwood Limited, Chichester, UK).Google Scholar
• Haemers WH (1995) Interlacing eigenvalues and graphs. Linear Algebra Appl. 227/228:593–616.Crossref, Google Scholar
• Harary F (1967) Problem 16. Fiedler M, ed. Theory of Graphs and Its Applications (Czechoslovak Academy of Science, Prague), p. 161.Google Scholar
• Harper LH (1964) Optimal assignments of numbers to vertices. J. SIAM 12(1):131–135.Google Scholar
• Harper LH (1966) Optimal numberings and isoperimetric problems on graphs. J. Combin. Theory 1(3):385–393.Crossref, Google Scholar
• Harper LH (2003) On the bandwidth of a Hamming graph. Theoret. Comput. Sci. 301:491–498.Crossref, Google Scholar
• Helmberg C, Rendl F, Mohar B, Poljak S (1995) A spectral approach to bandwidth and separator problems in graphs. Linear Multilinear Algebra 39(1–2):73–90.Crossref, Google Scholar
• Hendrich U, Stiebitz M (1992) On the bandwidth of graph products. J. Inform. Process. Cybern. 28(3):113–125.Google Scholar
• Higman DG (1970) Coherent configurations I. Rend. Sem. Mat. Univ. Padova XLIV:1–25.Google Scholar
• Higman DG (1987) Coherent algebras. Linear Algebra Appl. 93:209–239.Crossref, Google Scholar
• Hochberg R, McDiarmid C, Saks M (1995) On the bandwidth of triangulated triangles. Discrete Math. 138(1/3):261–265.Crossref, Google Scholar
• Hwang FK, Lagarias JC (1977) Minimum range sequences of all k-subsets of a set. Discrete Math. 19(3):257–264.Crossref, Google Scholar
• Juvan M, Mohar B (1993) Laplace eigenvalues and bandwidth-type invariants of graphs. J. Graph Theory 17(3):393–407.Crossref, Google Scholar
• Lai YL, Williams K (1999) A survey of solved problems and applications on bandwidth, edgesum and profiles of graphs. J. Graph Theory 31(2):75–94.Crossref, Google Scholar
• Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. Proc. CACSD Conf., Taipei, Taiwan, 284–289.Crossref, Google Scholar
• Monien B (1986) The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Algebra Discr. 7(4): 505–512.Crossref, Google Scholar
• Papadimitriou CH (1976) The NP-completeness of the bandwidth minimization problem. Computing 16(3):263–270.Crossref, Google Scholar
• Povh J, Rendl F (2007) A copositive programming approach to graph partitioning. SIAM J. Optim. 18(1):223–241.Crossref, Google Scholar
• Povh J, Rendl F (2009) Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6(3):231–241.Crossref, Google Scholar
• Rendl F, Sotirov R (2007) Bounds for the quadratic assignment problem using the bundle method. Math. Program. Ser. B 109(2–3): 505–524.Crossref, Google Scholar
• Smithline L (1995) Bandwidth of the complete k-ary tree. Discrete Math. 142(1–3):203–212.Crossref, Google Scholar
• Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds. Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, Internat. Ser. ORMS, Vol. 166 (Springer, New York), 795–820.Crossref, Google Scholar
• Sotirov R (2014) An efficient semidefinite programming relaxation for the graph partition problem. INFORMS J. Comput. 26(1):16–30.Link, Google Scholar
• Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12:625–653.Crossref, Google Scholar
• Wedderburn JHM (1907) On hypercomplex numbers. Proc. Lond. Math. Soc. 6(2):77–118.Google Scholar
• Wolkowicz H, Zhao Q (1999) Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96/97:461–479.Crossref, Google Scholar
• Zhao Q, Karisch SE, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2:71–109.Crossref, Google Scholar