×

zbMATH — the first resource for mathematics

Explicit concentrators from generalized N-gons. (English) Zbl 0554.05045
Concentrators are graphs used in the construction of switching networks that exhibit high connectivity. In this paper a technique for establishing the concentration properties of a bipartite graph by analysis of its eigenvalues is given. By identifying the points of a generalized N-gon with input nodes and lines of the N-gon with output nodes, the generalized N-gon defines a bipartie graph G for which the eigenvalues are well-known. The author shows that the generalized N-gons are excellent concentrators. While very large N-gons can be constructed, by the Feit-Higman theorem N-gons do not exist for arbitrarily large N, nor for arbitrary node degree. Hence the obtained results fall short of giving an asymptotic contruction.
Reviewer: J.A.Thas

MSC:
05C40 Connectivity
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
51E30 Other finite incidence structures (geometric aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bassalygo, L. A.; Pinsker, M. S., The complexity of an optimal non-blocking commutation scheme without reorganization, Problemy Peredači Informacii, 9, 84, (1973) · Zbl 0327.94051
[2] Biggs, Norman, Algebraic graph theory, (1974) · Zbl 0284.05101
[3] Cvetkovic, D. M.; Doob, M.; Sachs, H., Spectra of graphs, 368, (1980) · Zbl 0458.05042
[4] Dembowski, P., Finite geometries, (1968) · Zbl 0159.50001
[5] Feit, Walter; Higman, Graham, The nonexistence of certain generalized polygons, J. Algebra, 1, 114, (1964) · Zbl 0126.05303
[6] Gabber, Ofer; Galil, Zvi, Explicit constructions of linear size superconcentrators, 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979), 364, (1979), IEEE, New York · Zbl 0487.05045
[7] Haemers, W., Eigenvalue techniques in design and graph theory, 50, (1980) · Zbl 0429.05013
[8] Upper and lower bounds on time-space tradeoffs in a pebble gameReport79-745Dept. Computer Science, Stanford Univ.Stanford, CA1979July
[9] MacWilliams, R. J.; Sloane, N. J. A., The Theory of Error-Correcting Codes, 651, (1977) · Zbl 0369.94008
[10] Margulis, G. A., Explicit constructions of expanders, Problemy Peredači Informacii, 9, 71, (1973) · Zbl 0312.22011
[11] Space bounds for a game on graphsEighth Annual ACM Symposium on Theory of Computing (Hershey, Pa., 1976)Assoc. Comput. Mach., New York1976149160May
[12] Pippenger, N., Complexity theory, 114, (1978)
[13] Pippenger, Nicholas, Superconcentrators, SIAM J. Comput., 6, 298, (1977) · Zbl 0361.05035
[14] Pippenger, Nicholas, Generalized connectors, SIAM J. Comput., 7, 510, (1978) · Zbl 0385.05036
[15] Tanner, R. Michael, A recursive approach to low complexity codes, IEEE Trans. Inform. Theory, 27, 533, (1981) · Zbl 0474.94029
[16] On non-linear lower bounds in computational complexitySeventh Annual ACM Symposium on Theory of Computing (Albuquerque, N. M., 1975)Assoc. Comput. Mach., New York19754553
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.