Large fault-tolerant interconnection networks

Akers, S.B., Harel, D., Krishnamurthy, B.: The star graph: an attractive alternative to then-cube. 16th Conf. on Parallel Processing, 1987, pp. 393–400

Akers, S.B., Krishnamurthy, B.: On group graphs and their fault tolerance. IEEE Trans. Comput.C-36, 885–888 (1987)

Amar, D.: On the connectivity of some telecommunication networks. IEEE Trans. Comput.C-32, 512–519 (1983)

Ameter, D., de Gree, Max: Graphs and Interconnection networks. (Forthcoming book)

Berge, C.: Graphs and hypergraphs. New-York: North-Holland Publishing Co. (1973)

Bermond, J.-C., Homobono, N., Peyrat, C.: Large fault-tolerant interconnection networks. LRI Research Report, 1986

Bermond, J.-C., Bollobas, B.: The diameter of graphs- a survey. Proc. 12-th Southeastern Conference, Congressus Num.32, 3–27 (1981)

Bermond, J.-C., Bond, J., Paoli, M., Peyrat, C.: Graphs and interconnection networks: diameter and vulnerability. In surveys in combinatorics: Proc. 9-th British Combinatorial Conference, London Math. Soc., Lec. Notes Ser.82, 1–30 (1983)

Bermond, J.-C., Comellas, F., Hsu, F.: Distributed loop computer networks: a survey. IEEE trans. Comput. (1988) (submitted)

Bermond, J.-C., Delorme, C., Quisquater, J.-J.: Strategies for interconnection networks: some methods from graph theory. J. of Parallel and Distributed Comput.3, 433–449 (1986)

Bermond, J.-C., Favaron, O., Maheo, M.: Hamiltonian decomposition of Cayley graphs of degree four. J. Comb. Theory (B) (1988)

Bermond, J.-C., Illiades, G., Peyrat, C.: An optimization problem in distributed loop computer networks. In: Proc. third international conference on combinatorial math., New York, 1985, Annals N.Y. Acad. Science (1988)

Bhatt, S., Chung F.R.K., Leighton, T., Rosenberg, A.: Optimal simulations of tree machines. Proc. FOCS. pp. 274–282 (1986)

Boesch, F.T.: Graph theoretic models for network reliability studies. Stevens Institute of technology, electrical engineering and computer science department, Technical Report 8010, 1980

Boesch, F.T., Tindell, R.: Circulants and their connectivities. J. Graph Theory8, 487–499 (1984)

Boesch, F.T., Wang, J.: Reliable circulant networks with minimum transmission delay. IEEE Trans. Circuits Syst.CAS-32, 1286–1291 (1985)

Bollobas, B.: Graphs with given diameter and minimal degree. Ars Comb.2, 3–9 (1976)

Bond, J., Delorme, C., de la Vega, W.F.: Large Cayley graphs with small degree and diameter. LRI Research report 392, 1987

Bond, J., Peyrat, C.: Diameter vulnerability in networks. In: Proc. of Kalamazoo Colloquium 1984, Graph theory and its applications to algorithms and computer science. pp. 123–149, New York: Wiley 1985

Bond, J., Peyrat, C.: Diameter vulnerability of some large interconnection networks, The 19-th Southeastern Conference on Combinatorics, Graph Theory and Computing. Baton rouge, 1988

Bondy, J.A., Hell, P.: Counterexamples to theorems of Menger type for the diameter. Discrete Math.44, 217–220 (1983)

Boyles, S.M., Exoo, G.: A counterexample to a conjecture on paths of bounded length. J. Graph Theory6, 205–209 (1982)

Broder, A., Dolev, D., Fischer, M., Simons, B.: Efficient fault-tolerant routings in networks. In: Proc. ACM 16-th STOC. pp. 536–541. (1984)

de Bruijn, N.G.: A combinatorial problem. Koninklijke Nederlandse Academie van Wetenschappen Proc.A49, 758–764 (1946)

Campbell, L., Carlsson, G.E., Faber, V., Fellows, M.R., Langston, M.A., Moore, J.W., Mullhaupt, A.P., Sexton, H.B.: Dense symmetric networks from linear groups and codes (1988) (preprint)

Carlsson, G.E., Cruthirds, J.E., Sexton, H.B., Wright, C.G. Interconnection networks based on a generalization of cube-connected cycles. IEEE Trans. Comput.C-34, 769–772 (1985)

Chudnovsky, D.V., Chudnovsky, G.V., Denneau, M.M.: Regular graphs with small diameter as models for interconnection networks in 3rd Int. Conf. on Supercomputing Boston, 232–239 (1988)

Chung, F.R.K.: Diameter of communication networks. Proceedings of Symposia in Applied Mathematics34, 1–18 (1986)

Chung, F.R.K.: Diameters of graphs: old problems and new results. In: Proc. 18-th southeastern conference on Combinatorics, Graph theory and Computing Congresses Numeration 60, 295–317 (1987)

Chung, F.R.K.: Graphs with small diameter after edge deletion (1988) (preprint)

Chung, F.R.K., Coffman, E.G., Reiman, M.I., Simon, B.E.: The forwarding index of communication networks. IEEE Trans. Informat. Theory.IT-33, 224–232 (1987)

Chung, F.R.K., Garey, M.R.: Diameter bounds for altered graphs. J. Graph Theory8, 511–534 (1984)

Colbourn, C.J.: The Combinatorics of Networks Reliability. Oxford: Oxford University Press 1987

Dolev, D., Halpern, J., Simons, B., Strong, R.: A new look at fault-tolerant network routings. In: Proc. ACM, 16-th STOC. 526–535, 1984

van Doorn, E.A.: Connectivity of circulant digraphs. J. Graph Theory10, 9–14 (1986)

Du, D.Z., Hsu, D.F., Hwang, F.K.: Doubly-linked ring networks. IEEE Trans. Comput.C-34, 853–855 (1985)

Du, D.Z., Hsu, D.Z., Hwang, F.K., Zhang, X.M.: The hamiltonian property of generalized de Bruijn digraphs. J. Comb. Theory (to appear)

Du, D.Z., Hwang, F.K.: Generalized de Bruijn digraphs. Networks 18, 27–38 (1988)

Dwork, C., Peleg, D., Pippenger, N., Upfal, E.: Fault tolerance in networks of bounded degree. SIAM J. Comput. (to appear)

Entringer, R.C., Jackson, D.E., Slater, P.J.: Geodetic connectivity of graphs. IEEE Trans. Circuits Syst.Cas-24, 460–463 (1977)

Escudero, M., Fabrega, J., Morillo, P.: Fault-tolerant routings in double-loop networks, In: Proc. 11-th British Combinatorical Conference 1987, Ars Comb. (to appear)

Esfahanian, A.H.: Lower-bounds on the connectivities of a graph. J. Graph Theory9, 503–511 (1985)

Esfahanian, A.H., Hakimi, S.L.: Fault-tolerant routing in de Bruijn communication networks. IEEE Trans. Comput.C-34, 777–788 (1985)

Exoo, G.: On a measure of communication network vulnerability. Networks12, 405–409 (1982)

Fábrega, J., Fiol, M.A., Escudero, M.: The connectivity of iterated line digraphs. Submitted to J. of Graph Theory

Fábrega, J., Fiol, M.A., Yebra, J.L.A., Alegre, I.: Connectivity and reliable routing algorithms in line digraphs. In: Proc. 3rd Int. Symp. Applied Informatics, pp. 45–50. Switzerland: Grindenwald 1985

Faudree, R.J., Ordman, E.T., Schelp, R.H., Jacobson, M.S., Tuza, Z.: Menger's theorem and short paths. J. Comp. Math. and Comp. Combinatorics2, 235–253 (1987)

Favaron, O., Kouider, M., Maheo, M.: Edge-vulnerability and mean distance. Networks (to appear)

Feldman, P.: Fault tolerance of minimal path routings in a network. In: Proc. 17-th STOC, pp. 327–334, 1985

Fiol, M.A., Fábrega, J., Homobono, N., Escudero, M.: On surviving route graphs of iterated line digraphs. Submitted to Proc. of Kalamazoo Colloquium (1988)

Fiol, M.A., Yebra, A., Alegre, I., Valero, M.: A discrete optimization problem in local networks and data alignment. IEEE Trans. Comput.C-36, 702–713 (1987)

Fiol, M.A., Yebra, J.L.A., Alegre, I.: Line digraph iterations and the (d, k) digraph problem. IEEE Trans. Computer.C-33, 400–403 (1984)

Gomez, J.: Diametroy vulnerabilidad en redes de interconexion. Thesis, Universitat Politecnica de Catalunya, Barcelona, September 1986

Greenberg, D.S., Heath, L.S., Rosenberg, A.: Optimal embeddings of the FFT graph in the hypercube (1988) (preprint)

Hamidoune, Y.O.: On the connectivity of Cayley digraphs. Europ. J. Comb.5, 309–312 (1984)

Hartman, J., Rubin, I.: On diameter stability of graphs. Lect. Notes Math.642, 247–254 (1976)

Heydemann, M.C., Meyer, J.-C., Opatrny, J., Sotteau, D.: Consistent routings and forwarding indices (1988) (preprint)

Heydemann, M.C., Meyer, J.-C., Sotteau, D.: On forwarding indices of networks. Discrete App. Math. (1988)

Hillis, W.D.: The connection machine. In: ACM Distinguished Dissertation. The MIT press (1985)

Homobono, N.: Resistance aux pannes de grands reseaux d'interconnection. These de troisieme cycle, Universite de Paris-sud, LRI 1987

Homobono, N.: Connectivity of the undirected Imase and Itoh networks. In: Proc. 11-th British Conference, Ars Comb.25C, 179–194 (1988)

Homobono, N., Peyrat, C.: Fault-tolerant routings in Kautz and de Bruijn digraphs. (To appear in the Combinatorial conference, Montreal, Quebec, 1987)

Homobono, N., Peyrat, C.: Connectivity of Imase and Itoh digraphs. IEEE Trans. Comput.37, 1459–1461 (1988)

Imase, M., Itoh, M.: Design to minimize a diameter on building block network. IEEE Trans. Comput.C-30, 439–443 (1981)

Imase, M., Itoh, M.: A design for directed graphs with minimum diameter. IEEE Trans. Comput.C-32, 782–784 (1983)

Imase, M., Manabe, Y.: Fault tolerant routing in ak-connected network. Information Processing Letters, 1988

Imase, M. Soneoka, T., Okada, K.: Connectivity of regular directed graphs with small diameter. IEEE Trans. Comput.C-34, 267–273 (1985)

Imase, M., Soneoka, T., Okada, K.: A fault tolerant processor interconnection network. Denshi Tsushin Gakkai RonbunshiJ68-D, 8, 1449–1456 (in Japanese; translated in Systems and Computers in Japan, vol.17, No. 8, 21–30, 1986.)

Itai, A., Perl, Y., Shiloach, Y.: The complexity of finding maximum disjoint paths with length constraints. Networks12, 277–286 (1982)

Jolivet, J.-L.: Sur la connexite des graphes orientes. C.R. Acad. Sci., Paris,274A, 148–150 (1972)

Kautz, W.H.: Bounds on directed (d, k) graphs. Theory of cellular logic networks and machines, AFCRL-68-0668 Final Report, pp. 20–28, 1968

Kerjouan, R.: The edge-vulnerability of the diameter of interconnection networks. LRI Research Report 261, 1986, J. Graph Theory (submitted)

Krishnamoorthy, M.S., Krishnamurthy, B.: Fault diameter of interconnection networks. Comput. Math. Applic.13, 577–582 (1987)

Kumar, V.P., Reddy, S.M.: A class of graphs for fault-tolerant processor interconnections. In: IEEE 1984 Int. Conf. Distributed Computing Systems, pp. 448–460, 1984

Lovász, L., Neumann-Lara, V., Plummer, M.: Mengerian theorems for paths of bounded length. Period. Math. Hung.9, 269–276 (1978)

Mader, W.: Uber den Zusammenhang symmetrischer Graphen. Arch. Math.21, 331–336 (1970)

Mader, W.: Minimalen-fach kantenzusammenhängende Graphen. Math. Ann.191, 21–28 (1971)

Mader, W.: Connectivity and edge-connectivity in finite graphs. In: Surveys in Combinatorics: Proc. Seventh British Combinatorial Conference, Cambridge 1979, pp. 66–95. London Math. Soc. Lect. Note Ser.38, (1979)

Manabe, Y., Imase, M., Soneoka, T.: Reliable and efficient fixed routings in digraphs. Invited paper, IECIE, Japan 1988

Meyer, F.J., Pradhan, D.K.: Flip-trees: fault-tolerant graphs with wide containers. IEEE Trans. Comput.37, 472–478 (1988)

Morillo, P., Comellas, F., Fiol, M.A.: Diameter, mean distance and vulnerability of some graphs related to plane tesselations. Submitted to J. Graph Theory

Morillo, P., Fiol, M.A., Guitart, J.: On the (d, D, D, s)-digraph problem. 5th Int. Conf. on Applied Algebra, Error-Correcting Codes and Cryptography, AAECC-5, 1987

Opatrny, J.: A new family of 3-regular network models. In: Proc. of Int. Computer Symposium, Taiwan, pp. 1397–1401, 1986

Opatrny, J., Srinivasan, N., Alagar, V.S.: Highly fault-tolerant communication networks models. Submitted to IEEE on Circuits and System

Peleg, D., Simons, B.: On fault tolerant routings in general networks. PODCS, pp. 98–107, 1986

Peyrat, C.: Diameter vulnerability of graphs. Discrete Appl. Math.9, 245–250 (1984)

Plesnik, J.: Note on diametrally critical graphs. In: Recent Advances in Graph Theory, Proc. 2-nd Czechoslovak Symp., Prague 1974, Academia Prague, pp. 455–465, 1975

Plesnik, J.: Critical graphs of given diameter Acta Fac. Rerum Natur. Univ. Com. Mat.,30, 71–93 (1975)

Pradhan, D.K.: Interconnecting topologies for fault-tolerant parallel and distributed architectures. In: Proc. ICPP, pp. 238–242, 1981

Pradhan, D.K.: On a class of fault-tolerant multiprocessor network architectures. In: 3rd Int. Conf. on Distributed Processing, Miami, Floride, 1982

Pradhan, D.K.: Fault-tolerant Computing. Theory and Techniques, Englewood Cliffs, NJ, Prentice-Hall, 1986.

Pradhan, D.K., Reddy, S.M.: A Fault-tolerant communication architecture for distributed sustems. IEEE Trans. Comput.C-31, 863–870 (1982)

Preparata, F.R., Vuillemin, J.: The cube connected cycles: a versatile network for parallel computation. Commun. ACM24, 300–309 (1981)

Quaife, H.J.: On (d, k, μ) graphs, IEEE Trans. Comput.C-18, 270–272 (1969)

Reddy, S.M., Kuhl, J.G., Hosseini, S.H., Lee, H.: On digraphs with minimum diameter and maximum connectivity. In: Proceedings of 20-th Annual Allerton Conference, pp. 1018–1026, 1982

Reddy, S.M., Pradhan, D.K., Kuhl, J.G.: Directed graphs with minimal diameter and maximum node connectivity. School of Engineering Oakland Univ., Tech. Rep., 1980

Ronen, D., Perl, Y.: Heuristics for finding a maximum number of disjoint bounded paths. Networks14, 531–544 (1984)

Schlumberger, M.: De Bruijn communications networks. Standford PhD Thesis, Computer Science Department, Stanford, California, 1974

Schlumberger, M.: Connectivity of de Bruijn networks. Rapport de Recherche 154 Ensimag, Universite de Grenoble, 1978

Schoone, A.A., Bodlaender, H.L., van Leeuwen, J.: Diameter increase caused by edge deletion. J. Graph Theory11, 409–427 (1987)

Schumacher, U.: An algorithm for construction of ak-connected graph with minimum number of edges and quasiminimal diameter. Networks14, 63–74 (1984)

Sengupta, A., Sen, A., Bandyopadhyay, S.: On an optimally fault-tolerant multiprocessor network architecture. IEEE trans. Comp.C-36, 619–623 (1987)

Soneoka, T., Imase, M., Manabe, Y.: Design of ad-connected digraph with a minimum number of edges and a quasiminimal diameter, Part II. Submitted to Networks

Soneoka, T., Nakada, H., Imase, M.: Sufficient conditions for dense graphs to be maximally connected. In: Proc. of ISCAS 85, pp. 811–814, 1985

Soneoka, T., Nakada, H., Imase, M.: Design of ad-connected digraph with a minimum number of edges and quasiminimal diameter. Submitted to Discrete Appl. Math.

Soneoka, T., Nakada, H., Imase, M., Peyrat, C.: Sufficient conditions for maximally connected dense graphs. Discrete Math.63, 53–66 (1987)

Suurballe, J.W.: Disjoint paths in a network. Networks4, 125–145 (1974)

Vijayan, K., Murty, U.S.R.: On accessibility in graphs. Sankhya Ser. A,26, 299–302 (1964)

Wagner, A.: Embedding arbitrary binary trees in a hypercube. Submitted to J. Parallel and Distributed Computing

Watkins, W.E.: Connectivity of transitive graphs. J. Comb. Theory8, 23–29 (1970)

Wong, C.K., Coppersmith, D.: A combinatorial problem related to multimodule memory organizations. J. of Association for Communication for Computing Machinery21, 392–402 (1974)