Abstract
The construction of large networks with small diameter D for a given maximal degree Δ is a major goal in combinatorial network theory. Using genetic algorithms, together with Cayley graph techniques, new results for this degree/diameter problem can be obtained. A modification of the Todd-Coxeter algorithm yields further results and allows, with Sabidussi's representation theorem, a uniform representation of vertex-symmetric graphs. The paper contains an updated table of the best known (Δ, D)-graphs and a table with the largest known graphs for a given Δ and maximum average distance µ between the nodes.
Preview
Unable to display preview. Download preview PDF.
References
Bruce W. Arden and K. Wendy Tang. IEEE Transactions on Communications, 39(11):1533–1537, November 1991.
J. C. Bermond, C. Delorme, and G. Farhi. Large graphs with given degree and diameter III. Annals of Discrete Mathematics, 13:23–32, 1982.
J. C. Bermond, C. Delorme, and G. Farhi. Large graphs with given degree and diameter. II. iJournal of Combinatorial Theory, Series B, 36:32–48, 1984.
Jean-Claude Bermond and Béla Bollobás. The diameter of graphs–A survey. Congressus Numerantium, 3:3–27, 1981.
Jean-Claude Bermond, Charles Delorme, and J.-J. Quisquater. Strategies for interconnection networks, some results from graph theory. Journal of Parallel and Distributed Computing, 3:433–449, 1986.
Norman Biggs. Algebraic Graph Theory. Cambridge University Press, 2nd edition, 1993.
Shahid H. Bokhari and A. D. Raza. Reducing the diameters of computer networks. IEEE Transactions on Computers, C-35(8):757–761, August 1986.
Lowell Campbell et al. Small diameter symmetric networks from linear groups. IEEE Transactions on Computers, 41(2):218–220, 1992.
Alan G. Chalmers and Steve Gregory. Constructing minimum path configurations for multiprocessor systems. Parallel Computing, 19:343–355, 1993.
Fan R. K. Chung. Diameters of graphs: Old and new results. Congressus Numerantium, 60:295–317, 1987.
F. Comellas and J. Gómez. New large graphs with given degree and diameter. In Y. Alavi and A. Schwenk, editors, Graph Theory, Combinatorics and Algorithms, volume 1, pages 221–233, New York, 1995. John Wiley & Sons, Inc.
Francesc Comellas. comellas@mat.upc.es.
Robert Cypher, Friedhelm Meyer auf der Heide; Christian Scheideler, and Berthold Vöcking. Universal algorithms for store-and-forward and wormhole routing. In Proceedings of the 26th ACM-STOC, pages 356–365, 1996.
C. Delorme. Examples of products giving large graphs with given degree and diameter. Discrete Applied Mathematics, 37/38:157–167, 1992.
Charles Delorme.cd@Iri.fr.
Charles Delorme and G. Farhi. Large graphs with given degree and diameter — part I. IEEE Transactions on Computers, C-33(9):857–860, September 1984.
Michael J. Dinneen and Paul R. Hafner. New results for the degree/diameter problem. Networks, 24:359–367, 1994.
Geoffrey Exoo. Applying optimization algorithms to Ramsey problems. In Yousef Alavi, editor, Graph Theory, Combinatorics, Algorithms and Applications, pages 175–179. John Wiley & Sons, Inc, New York, 1991.
H. Felsch. Programmierung der Restklassenabzählung einer Gruppe nach Untergruppen. Numerische Mathematik, 3:250–256, 1961.
P. Hafner. Large Cayley graphs and digraphs for the degree/diameter problem: an update. (in preparation), 1997.
Berthold Hagmann. Optimierungstechniken zum Entwurf günstiger Netztopologien mittels Cayley-Graphen. Diploma thesis, Universität Oldenburg, 1997.
J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 1975.
S. Lakshmivarahan, Jung-Sing Jwo, and S. K. Dhall. Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey. Parallel Computing, 19:361–407, 1993.
John Leech. Coset enumeration. In Michael D. Atkinson, editor, Computational Group Theory, pages 3–18. Academic Press, 1984.
F. Thomson Leighton. Parallel Algorithms and Architectures. Morgan Kaufmann Publishers, San Mateo, California, 1992.
Gerard Memmi and Yves Raillard. Some new results about the (d, k) graph problem. IEEE Transactions on Computers, C-31(8):784–791, August 1982.
Friedhelm Meyer auf der Heide and Berthold Vocking. A packet routing protocol for arbitrary networks. In E. W. Mayr and C. Puech, editors,Proceedings of the 12th Annual Symposium on Theoretical Aspects of Computer Science (STACS '95), LNCS 900, pages 291–302, 1995.
Gert Sabidussi. Vertex-transitive graphs. Monatshefte für Mathematik, 68:426–438, 1964.
Michael Sampels. Algebraic constructions of efficient systolic architectures. In Proceedings of the 2nd International Conference on Massively Parallel Computing Systems (MPCS '96), pages 15–22. IEEE Computer Society Press, 1996.
Michael Sampels. Cayley graphs as interconnection networks: A case study. In Proceedings of the 7th International Workshop on Parallel Processing by Cellular Automata and Arrays (PARCELLA '96), pages 67–76, Berlin, 1996. Akademie-Verlag.
Michael Sampels. Massively parallel architectures and systolic communication. In Proceedings of the 5th Euromicro Workshop on Parallel and Distributed Processing (PDP '97), pages 322–329. IEEE Computer Society Press, 1997.
Michael Sampels. Representation of vertex-symmetric interconnection networks. In Proceedings of the 2nd International Conference on Parallel Processing & Applied Mathematics. (to appear), 1997.
Michael Sampels and Stefan Schöf. Massively parallel architectures for parallel discrete event. simulation. In Proceedings of the 8th European Simulation Symposium (ESS '96), volume 2, pages 374–378. SCS, 1996.
Christian Scheideler and Berthold Vöcking. Universal continuous routing strategies. In Proceedings of the 8th ACM-SPAA, pages 142–151. ACM, 1996.
Martin Schönert. GAP — groups, algorithms and programming. Lehrstuhl D für Mathematik, RWTH Aachen, 1995.
Robert M. Storwick. Improved construction techniques for (d, k) graphs. IEEE Transactions on Computers, C-19:1214–1216, December 1970.
J. A. Todd and H. S. M. Coxeter. A practical method for enumerating cosecs of a finite abstract group. Proceeding of the Edinburgh Mathematical Society, 5(2):26–34, 1936.
Lutz Twele. Effiziente Implementierung des Todd-Coxeter Algorithmus im Hinblick auf Grad/Durchmesser-Optimierung von knotentransitiven Graphen. Diploma thesis, Universität Oldenburg, 1997.
Otto Wohlmuth. A new dense group graph discovered by an evolutionary approach. In Paralleles und Verteiltes Rechnen, Beiträge zum 4. Workshop über wissenschaftliches Rechnen. Shaker Verlag. 1996.
H. P. Yap. Some topics in graph theory. London Mathematical Society Lecture Note Series 108. Cambridge University Press, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sampels, M. (1997). Large networks with small diameter. In: Möhring, R.H. (eds) Graph-Theoretic Concepts in Computer Science. WG 1997. Lecture Notes in Computer Science, vol 1335. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0024505
Download citation
DOI: https://doi.org/10.1007/BFb0024505
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63757-8
Online ISBN: 978-3-540-69643-8
eBook Packages: Springer Book Archive