Upper bounds on the bisection width of 3- and 4-regular graphs

Alon, 1997, On the edge-expansion of graphs, Combinator. Probab. Comput., 6, 145, 10.1017/S096354839700299X Bui, 1987, Graph bisection algorithms with good average case behaviour, Combinatorica, 7, 171, 10.1007/BF02579448 Bezroukov, 2000, New spectral lower bounds on the bisection width of graphs, vol. 1928, 23 C.F. Bornstein, A. Litman, B.M. Maggs, R.K. Sitaraman, T. Yatzkar, On the bisection width and expansion of butterfly networks, in: Proc. Int. Parallel Processing Symp. (IPPS), 1998, pp. 144–150 Bollobas, 1988, The isoperimetric number of random regular graphs, European J. Combin., 9, 241, 10.1016/S0195-6698(88)80014-3 Clark, 1988, The bisection width of cubic graphs, Bull. Austral. Math. Soc., 39, 389, 10.1017/S0004972700003300 Chiu, 1992, Cubic Ramanujan graphs, Combinatorica, 12, 275, 10.1007/BF01285816 Diekmann, 1995, Using helpful sets to improve graph bisections, vol. 21, 57 Fiedler, 1975, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Math. J., 25, 619, 10.21136/CMJ.1975.101357 U. Feige, R. Krauthgamer, A polylogarithmic approximation of the minimum bisection, in: Proc. Symp. on Foundations of Computer Science (FOCS), 2000, pp. 105–115 Garey, 1976, Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237, 10.1016/0304-3975(76)90059-1 B. Hendrickson, R. Leland, The chaco user's guide: Version 2.0, Technical Report SAND94-2692, Sandia National Laboratories, Albuquerque, NM, 1994 Hromkovič, 1992, The bisection problem for graphs of degree 4 (configuring transputer systems), 215 Holton, 1993 Karypis, 1998 Kostochka, 1992, On bounds of the bisection width of cubic graphs, 151 Kostochka, 1993, On a lower bound for the isoperimetric number of cubic graphs, vol. 1, 251 Lubotzky, 1988, Ramanujan graphs, Combinatorica, 8, 261, 10.1007/BF02126799 Margulis, 1988, Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, Probl. Inf. Transm., 24, 39 B. Monien, R. Diekmann, A local graph partitioning heuristic meeting bisection bounds, in: 8th SIAM Conf. on Parallel Processing for Scientific Computing, 1997 Manabe, 1994, The minimum bisection widths of the cube-connected cycles graph and cube graph, Trans. IEICE, J67-D, 647 Morgenstern, 1994, Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q, J. Combin. Theory Ser. B, 62, 44, 10.1006/jctb.1994.1054 Monien, 2001, Bisection width of 3- and 4-regular graphs, vol. 2136, 524 Monien, 2000, Quality matching and local improvement for multilevel graph-partitioning, Parallel Comput., 26, 1609, 10.1016/S0167-8191(00)00049-1 R. Preis, R. Diekmann, The PARTY partitioning-library, user guide, version 1.1, Technical Report TR-RSFB-96-024, Universität Paderborn, 1996 F. Pellegrini, SCOTCH 3.1 user's guide, Technical Report 1137-96, LaBRI, University of Bordeaux, 1996 R. Preis, Analyses and design of efficient graph partitioning methods, Heinz Nixdorf Institut Verlagsschriftenreihe, Dissertation, Universität Paderborn, Germany, 2000 Walshaw, 2000