Interconnection Network Seminar (CSE736)
SUBNET group
Spring 2002

• Here is a list of topics and papers suggested for your presentation. This list shall be improved and updated over the next 2, 3 weeks. Again, please feel free to pick your own topic and discuss it with me.
• Note: (*) means I have a hard copy of the paper, (x) means I consider the paper mathematically dense enough so that you can just present the paper alone without doing a survey on the topic. The more number of x's, the more I would like to see the paper presented.
• Lastly, the papers listed for a particular topic are, in some cases, not sufficient for a survey on that topic. They are listed as the first starting point.

1. Sorting Networks:

• (x) Adler, Micah; Byers, John W.; Karp, Richard M. Parallel sorting with limited bandwidth. SIAM J. Comput. 29 (2000), no. 6, 1997--2015 (electronic).
• (*) (xxx) Ajtai, M.; Komlós, J.; Szemerédi, E. Sorting in $c\,{\rm log}\,n$ parallel steps. Combinatorica 3 (1983), no. 1, 1--19.
• (x) Dyer, Martin E.; Sen, Sandeep Fast and optimal parallel multidimensional search in PRAMs with applications to linear programming and related problems. SIAM J. Comput. 30 (2000), no. 5, 1443--1461 (electronic).

2. Dynamic Routing:

• (x) Andrews, Matthew; Fernández, Antonio; Harchol-Balter, Mor; Leighton, Tom; Zhang, Lisa General dynamic routing with per-packet delay guarantees of $O({\rm distance}+1/{\rm session rate})$. SIAM J. Comput. 30 (2000), no. 5, 1594--1623 (electronic).
• F. T. Leighton, B. M. Maggs, and S. B. Rao, Packet routing and job-shop scheduling in $O(congestion + dilation)$ steps, Combinatorica, 14 (1994), pp. 167--186.
• M. Andrews, B. Awerbuch, A. Fernández, J. Kleinberg, T. Leighton, and Z. Liu, Universal stability results for greedy contention-resolution protocols, in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, Burlington, VT, 1996, pp. 380--389.
• (x) A. K. Parekh and R. G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: The single-node case, IEEE/ACM Trans. Networking, 1 (1993), pp. 344--357.
• (x) A. K. Parekh and R. G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: The multiple-node case, IEEE/ACM Trans. Networking, 2 (1994), pp. 137--150.

3. Gossiping:

• (x) Flammini, Michele; Pérennès, Stéphane On the optimality of general lower bounds for broadcasting and gossiping. SIAM J. Discrete Math. 14 (2001), no. 2, 267--282 (electronic).
• (x) J.-C. Bermond, L. Gargano, A. A. Rescigno, and U. Vaccaro, Fast gossiping by short messages, SIAM J. Comput., 27 (1998), pp. 917--941.
• (x) Fertin, Guillaume; Labahn, Roger Compounding of gossip graphs. Networks 36 (2000), no. 2, 126--137.
• S. T. Hedetniemi, S. M. Hedetniemi, and A. Liestman, A survey of gossiping and broadcasting in communication networks, Networks, 18 (1986), pp. 319--349.
• J. Hromkovi\v c, R. Klasing, E. Stohr, and H. Wagener, Gossiping in vertex-disjoint paths mode in $d$-dimensional grids and planar graphs, Inform. Comput., 123 (1995), pp. 17--28
• J. Hromkovi\v c, R. Klasing, W. Unger, and H. Wagener, Optimal algorithms for broadcast and gossip in the edge-disjoint path modes, Inform. Comput., 133 (1997), pp. 1--33.
• J. Hromkovi\v c, R. Klasing, B. Monien, and R. Peine, Dissemination of information in interconnection networks (broadcasting and gossiping), in Combinatorial Network Theory, Ding-Zhu Du and D. Frank Hsu, eds., Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995, pp. 125--212.
• D. W. Krumme, G. Cybenko, and K. N. Venkataraman, Gossiping in minimal time, SIAM J. Comput., 21 (1992), pp. 111--139.
• R. Labahn, S. Hedetniemi, and R. Laskar, Periodic gossiping on trees, Discrete Appl. Math., 53 (1994), pp. 235--246.
• A. Liestman and D. Richards, Network communication in edge-colored graphs: Gossiping, IEEE Trans. Par. Distr. Syst., 4 (1993), pp. 438--445.
• A. Liestman and D. Richards, Perpetual gossiping, Parallel Process. Lett., 3 (1993), pp. 347--355.
• (x) Fraigniaud and Peters, "Minimum Linear Gossip Graphs and Maximal Linear $(\Delta, k)$-Gossip Graphs", Networks (2001), Vol. 38 (3), pp 150--162.

3a Broadcasting in several topologies

• (x) S. Pérennès, Lower bounds on broadcasting time of de Bruijn networks, in Proceedings of the 2nd International Euro-Par Conference, Lecture Notes in Comput. Sci. 1123, Springer-Verlag, Berlin, 1996, pp. 325--332.
• (x) V. Sunderam and P. Winkler, Fast information sharing in a complete network, Discrete Appl. Math., 42 (1993), pp. 75--86
• J.-C. Bermond, P. Hell, A. Liestman, and J. G. Peters, Broadcasting in bounded degree graphs, SIAM J. Discrete Math., 5 (1992), pp. 10--24.
• J. Bermond, X. Munoz, and A. Marchetti-Spaccamela, Induced broadcasting algorithms in iterated line digraphs, in Proceedings of the 2nd International Euro-Par Conference, Lecture Notes in Comput. Sci. 1123, Springer-Verlag, Berlin, 1996, pp. 313--324.
• R. Klasing, B. Monien, R. Peine, and E. Stohr, Broadcasting in butterfly and de Bruijn networks, Discrete Appl. Math., 53 (1994), pp. 183--197.
• A. L. Liestman and J. G. Peters, Broadcast networks of bounded degree, SIAM J. Discrete Math., 1 (1988), pp. 531--540.

4. Misc. Network Theory

• (x) R. L. Cruz, A calculus for network delay, Part I: Network elements in isolation, IEEE Trans. Inform. Theory, 37 (1991), pp. 114--131.
• (x) R. L. Cruz, A calculus for network delay, Part II: Network analysis, IEEE Trans. Inform. Theory, 37 (1991), pp. 132--141.

5. Scheduling Communication with Deadlines

• Micah Adler, Arnold L. Rosenberg, Ramesh K. Sitaraman, and Walter Unger, Scheduling Time-Constrained Communication in Linear Networks. In Proceedings of 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1998.
• Micah Adler, Sanjeev Khanna, Rajmohan Rajaraman and Adi Rosen, Time-Constrained Scheduling of Weighted Packets on Trees and Meshes. In Proceedings of 11th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1999.
  
• M. Andrews, A. Fernandez, M. Harchol-Balter, F.T. Leighton, L. Zhang, General dynamic routing with per-packet delay guarantees of O(distance + 1/session rate). In 38th IEEE Symp. on Foundations of Computer Science 1997.
  
• M. Andrews and L. Zhang, Packet routing with arbitrary end-to-end delay requirements. In 31st ACM Symp. on Theory of Computing 1999.

6. Reliable Message Delivery

• Micah Adler, Yair Bartal, John W. Byers, Michael Luby, and Danny Raz, A Modular Analysis of Network Transmission Protocols. In Proceedings of 5th Israeli Symposium on Theory of Computing and Systems (ISTCS) 1997.
  
• Kushilevitz, Ostrovsky, and Rosen, Log-Space Polynomial End-to-End Communication. In 28th STOC, 1995, pages 559--568.
  
• Faith Fich, End-to-End Communication
• Micah Adler and Faith Fich, The Complexity of End-to-End Communication in Memoryless Networks. In Proceedings of 18th ACM Symposium on Principles of Distributed Computing (PODC) 1999.

7. Ad-Hoc Wireless Networks

• (x)R. Bar-Yehuda, O. Goldreich, A. Itai, On the time complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. J. Comput. and Syst. Sci. 45, pp. 104-126, 1992.
• (x)I. Gaber, Y. Mansour, Broadcast in radio networks. In Proceedings of Symposium on Discrete Algorithms, pp. 577-582, 1995.
  
• (x)L.M. Kirousis, E. Kranakis, D. Krizanc, A. Pelc, Power consumption in packet radio networks. In Proceedings of Symposium on Theoretical Aspects of Computer Science 1997.
• (x)Micah Adler and Christian Scheideler, Efficient Communication Strategies for Ad-Hoc Wireless Networks . In Proceedings of 10th ACM Symposium on Parallel Algorithms and Architectures (SPAA) 1998. Invited for submission to SPAA '98 special issue of Theory of Computing Systems.

8. Fairness / Compression

• (x) (Presenter: Jikai Li) J. Kleinberg, Y. Rabani, E. Tardos. Fairness in Routing and Load Balancing. Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS), 1999.

9. Error Correcting Codes

• (xx) Michael Sipser and Daniel A. Spielman, Expander Codes. In IEEE Transactions on Information Theory, 1996, Vol 42, No 6, pp. 1710-1722. Extended abstract in Proceedings of FOCS 94.
  
• (xx) Daniel A. Spielman, Linear-time encodable and decodable error-correcting codes. In IEEE Transactions on Information Theory, 1996, Vol 42, No 6, pp. 1723-1732. Extended abstract in Proceedings of STOC 95
  
• (x) Michael G. Luby, Michael Mitzenmacher, M. Amin Shokrollahi, and Volker Stemann, Practical Loss-Resilient Codes. In the Twenty-Ninth Annual ACM Symposium on Theory of Computing STOC 97.

10. Multicasting

• Sylvia Ratnasamy and Steven McCanne, Inference of Multicast Routing Trees and Bottleneck Bandwidths using End-to-end Measurements. Proceedings of INFOCOM '99, March 21, 1999, New York, NY.
• R. Caceres, N.G. Duffield, J. Horowitz, F. Lo Presti, D. Towsley, Loss-based Inference of Multicast Network Topology, to appear at IEEE CDC'99, December 1999
• Steven McCanne, Van Jacobson, and Martin Vetterli, Receiver-driven Layered Multicast. ACM SIGCOMM, August 1996, Stanford, CA, pp. 117-130.
• L. Vicisano, J. Crowcroft & L. Rizzo, TCP-like congestion control for layered multicast data transfer, In Proceedings IEEE InfoCom'98, March/April 1998, San Francisco.
  
• S. Paul, K. K. Sabnani, J. C. Lin and S. Bhattacharyya. Reliable Multicast Transport Protocol (RMTP). In IEEE Journal on Special Areas in Communications (JSAC), April 1997, 15:3 pp.407-421.
  
• (x) A. Bar-Noy, S. Guha, J. Naor, and B. Schieber, Multicasting in Heterogeneous Networks. In Proceedings of STOC 98.

11. Selection Networks

• (*) (xxx) Pippenger, Nicholas "Selection networks". SIAM J. Comput. 20 (1991), no. 5, 878--887.
• (x) Jimbo, S.; Maruoka, A. A method of constructing selection networks with $O(\log n)$ depth. SIAM J. Comput. 25 (1996), no. 4, 709--739.

12. (Widesense/strictly) Nonblocking Networks

• (x) Yang, Yuanyuan; Wang, Jianchao Wide-sense nonblocking Clos networks under packing strategy. IEEE Trans. Comput. 48 (1999), no. 3, 265--284.
• (x) Fingerhut, J. Andrew; Suri, Subhash; Turner, Jonathan S. Designing least-cost nonblocking broadband networks. J. Algorithms 24 (1997), no. 2, 287--309.
• (x) Fishburn, Peter; Hwang, F. K.; Du, D. Z.; Gao, B. On $1$-rate wide-sense nonblocking for $3$-stage Clos networks. Discrete Appl. Math. 78 (1997), no. 1-3, 75--87
• (x) Gao, B.; Hwang, F. K. Wide-sense nonblocking for multirate $3$-stage Clos networks. Theoret. Comput. Sci. 182 (1997), no. 1-2, 171--182.
• (*) Chung, Shun-Ping; Ross, Keith W. On nonblocking multirate interconnection networks. SIAM J. Comput. 20 (1991), no. 4, 726--736.
• (*) Melen, Riccardo; Turner, Jonathan S. Nonblocking multirate networks. SIAM J. Comput. 18 (1989), no. 2, 301--313.
• (*) (x) Richards, G. W.; Hwang, F. K. Extended generalized shuffle networks: sufficient conditions for strictly nonblocking operation. Advances in switching networks (Princeton, NJ, 1997), 15--48, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 42, Amer. Math. Soc., Providence, RI, 1998
• Schwill, Andreas Nonblocking graphs: greedy algorithms to compute disjoint paths. STACS 90 (Rouen, 1990), 250--262, Lecture Notes in Comput. Sci., 415, Springer, Berlin, 1990
• (*) Friedman, J. A lower bound on strictly nonblocking networks. Combinatorica 8 (1988), no. 2, 185--188.
• (*) Feldman, Paul; Friedman, Joel; Pippenger, Nicholas Wide-sense nonblocking networks. SIAM J. Discrete Math. 1 (1988), no. 2, 158--173.
• Hwang, F. K. Three-stage multiconnection networks which are nonblocking in the wide sense. Bell System Tech. J. 58 (1979), no. 10, 2183--2187.
• (*) Pippenger, Nicholas On rearrangeable and nonblocking switching networks. J. Comput. System Sci. 17 (1978), no. 2, 145--162.
• Smith, D. G. Lower bound on the size of a $3$-stage wide-sense nonblocking network. Electron. Lett. 13 (1977), no. 7, 215--216.
• (x) C. Zhou and Y. Yang, ``Wide-sense nonblocking multicast in a class of regular optical WDM networks,'' IEEE Transactions on Communications, vol. 50, no. 1, pp. 126-134, January 2002.

(On-line) Algorithms on Nonblocking Networks

• (xx) Arora, Sanjeev; Leighton, F. T.; Maggs, Bruce M. On-line algorithms for path selection in a nonblocking network. SIAM J. Comput. 25 (1996), no. 3, 600--625.
• (x)Lin, Geng; Pippenger, Nicholas Parallel algorithms for routing in nonblocking networks. ACM Symposium on Parallel Algorithms and Architectures (Hilton Head, SC, 1991). Math. Systems Theory 27 (1994), no. 1, 29--40.

13. Self-routing Networks

• (x) Hollmann, H. D. L.; van Lint, J. H., Jr. "Nonblocking self-routing switching networks." Discrete Appl. Math. 37/38 (1992), 319--340
• (x)Y. Yang, A New Self-Routing Multicast Network, IEEE Trans. on Parallel and Distributed Computing Systems, Vol 10, No. 11 (Dec 1999)

14. Concentrators - Superconcentrators - Expanders (limited here, there are tons of papers on this topic)

• (*) Chung, F. R. K. On concentrators, superconcentrators, generalizers, and nonblocking networks. Bell System Tech. J. 58 (1979), no. 8, 1765--1777.

15. Multicast/Broadcast Indirect Networks

• (x) Yang, Yuanyuan; Masson, Gerald M. The necessary conditions for Clos-type nonblocking multicast networks. IEEE Trans. Comput. 48 (1999), no. 11, 1214--1227.
• (x) Y. Yang, ``A class of interconnection networks for multicasting,'' IEEE Transactions on Computers, vol. 47, no. 8, August 1998, pp. 899-906.
• Y. Yang, J. Wang and C. Qiao, ``Nonblocking WDM multicast switching networks,'' IEEE Transactions on Parallel and Distributed Systems, vol. 11, no. 12, pp. 1274-1287, December 2000.
• Y. Yang, ``The performance of multicast banyan networks,'' Journal of Parallel and Distributed Computing, vol. 60, no. 8, pp. 909-923, August 2000.

16. Blocking Probability

• (x) Y. Yang and J. Wang, ``On blocking probability of multicast networks,'' IEEE Transactions on Communications, vol. 46, no. 7, July 1998, pp. 957-968.
• (x) M.P. Haynos and Y. Yang, ``An analytical model on the blocking probability of a fault-tolerant network,'' IEEE Transactions on Parallel and Distributed Systems, special issue on Fault-Tolerant Routing, vol. 10, no. 10, pp. 1040-1051, October 1999.
• (x) Y. Yang and J. Wang, ``A more accurate analytical model on blocking probability of multicast networks,'' IEEE Transactions on Communications, vol. 48, no. 11, pp. 1930-1936, Nov. 2000.
• (xx) Chung, Shun-Ping, Kashper, Arik, Ross, Keith W., "Computing approximate blocking probabilities for large loss networks with state-dependent routing", IEEE/ACM Transactions on Networking, Vol.1, No. 1 (Feb. 1993), pp. 105-115
• (x) Birman, A., "Computing approximate blocking probabilities for a class of all-optical networks", Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 2).
• (xx) T. Tripathi and K. N. Sivarajan. Computing Approximate Blocking Probabilities in Wavelength Routed All-Optical Networks with Limited-Range Wavelength Conversion. Proc. IEEE INFOCOM'99., March, 1999

17. Channel Assignment, Wavelength Assignment

• (x) Janssen, Jeannette; Narayanan, Lata Approximation algorithms for channel assignment with constraints. Theoret. Comput. Sci. 262 (2001), no. 1-2, 649--667.
• (x) Havet, Frédéric Channel assignment and multicolouring of the induced subgraphs of the triangular lattice. Graph theory (Prague, 1998). Discrete Math. 233 (2001), no. 1-3, 219--231.
• (xx) McDiarmid, Colin; Reed, Bruce Channel assignment and weighted coloring. Networks 36 (2000), no. 2, 114--117.
• (x) McDiarmid, Colin A doubly cyclic channel assignment problem. Discrete Appl. Math. 80 (1997), no. 2-3, 263--268.
• (x) Liu, Daphne Der-Fen $T$-graphs and the channel assignment problem. Discrete Math. 161 (1996), no. 1-3, 197--205.
• (x) Olariu, Stephan; Schwing, James L.; Zhang, Jingyuan A constant-time channel-assignment algorithm on reconfigurable meshes. BIT 32 (1992), no. 4, 586--597.
• (x) Xu, Li and Wang Dynamic Routing and Assignment of Wavelength Algorithms in Multi-fiber WDM Networks, IEEE Journal on Selected Areas in Communications, Vol 18, No. 10, 2030--2137, Oct 2000.
• (x) T Lee and K. Lee, Optimal Routing and Wavelength Assignment in WDM Ring Networks, IEEE Journal on Selected Areas in Communications (Oct 2000), Vol 18, No. 10, 2146--2154.
• (x) Law and Siu, Online Routing and Wavelength Assignment in Single-Hub WDM Ring, IEEE Journal on Selected Areas in Communications (Oct 2000), Vol 18, No. 10, 2111--2122.
• (x) Deng, Li and Zhang, Wavelength Allocation on Trees of Rings, Networks (2000), Vol 35 (4), pp. 248--252.
• R. Ramaswami and K. N. Sivarajan, "Routing and wavelength assignment in all-optical networks," IEEE/ACM Transactions on Networking, vol. 3, pp. 489--500, Oct 1995.
• D. Banerjee and B. Mukherjee, "A practical approach for routing and wavelength assignment in large wavelength-routed optical networks," IEEE Journal on Selected Areas in Communications, vol. 14, pp. 903--908, June 1996.
• (x) H. Harai, M. Murata and H. Miyahara, " Performance Analysis of Wavelength Assignment Policies in All-Optical Networks with Limited-Range Wavelength Conversion ," IEEE Journal of Selected Areas in Communication , volume 16, No.7, pages 1051--1060, September 1998.
• (x) L.W. Liu, P.-J. Wan, and O. Frieder, "Wavelength Assignment in WDM Rings to Minimize SONET ADMs", submitted for publication, 1999.
• O. Gerstel, P. Lin, and G. Sasaki. Wavelength Assignment in WDM Rings to Minimize System Cost instead of Number of Wavelengths, , INFOCOM'98.
• (x) G. Li and R. Simha. On bounds for the wavelength assignment problem in optical ring networks. Journal of HighSpeed Networks, to appear.
• (x) G. Li and R. Simha. New Results for the Wavelength Assignment Problem in Optical Networks. Accepted by ACM-SE'99.
• Guangzhi Li and Rahul Simha. A new algorithm for reducing the number of add-drop multiplexers in WDM optical ring networks. Submitted, 1999.

18. Charactering Indirect Network Topologies

• (x) Chang, Gerard J.; Hwang, Frank K.; Tong, Li-Da Characterizing bit permutation networks, Networks 33 (1999), no. 4, 261--267.
• (x) Hwang, Frank K.; Yen, Chi-Hung, "Characterizing bit permutation networks obtained from the line digraphs of bit permutation networks", Networks 38 (2001), no. 1, 1--5.

19. Some Problems in SONET/WDM Networks

• (x) C. Colbourn, P.-J. Wan: Minimizing Drop Cost for SONET/WDM Networks with 1/8 Wavelength Requirements, Networks (2001), 107-116.
• (x) P.-J. Wan, G. Calinescu, L.-W. Liu, O. Frieder: Grooming of Arbitrary Traffic in SONET/WDM Rings, IEEE Journal of Selected Area on Communications, Volume: 18, Issue: 10, October 2000, pp. 1995 -2003
• (x) Ruan, Lu; Du, Dingzhu; Hu, Xiaodong; Jia, Xiaohua; Li, Deying; Sun, Zheng Converter placement supporting broadcast in WDM optical networks. IEEE Trans. Comput. 50 (2001), no. 7, 750--758
• (x) D. Li, X. Du, X. Hu, L. Ruan and X. Jia, "Minimizing Number of Wavelengths in Multicast Routing Trees in WDM Networks", Networks, vol. 35, pp.260-265, July 2000.
• (x) Wan and Yang, "Load Balanced Routing in Counter Rotated SONET Rings", Networks (2000), Vol. 35, No. 4, pp. 279--286.
• B. Mukherjee, "WDM Optical Communication Networks: Progress and Challenges" (Invited Paper), IEEE Journal of Selected Area on Communications, October 2000, Volume 18, Number 10.
• (x) B. Beauquier, J.-C. Bermond, L. Gargano, P. Hell, S. Perennes, and U. Vaccaro. Graph problems arising from wavelength-routing in all-optical networks. Proc. of Workshop on Optics in Computer Science WOCS'97.

20. Fault-Tolerant Routing

• (x) Hong Shen, Francis Chin, Yi Pan, "Efficient Fault-Tolerant Routing in Multihop Optical WDM Networks", IEEE Trans. on Parallel and Distrib. Comput. Sys., October 1999 (Vol. 10, No. 10), pp pp. 1012-1025.
• (x) Barrière, Lali; Fàbrega, Josep; Simó, Ester; Zaragozá, Marisa Fault-tolerant routings in chordal ring networks. Networks 36 (2000), no. 3, 180--190
• Liu, Yu-Liang; Wang, Yue-Li; Guan, D. J. An optimal fault-tolerant routing algorithm for double-loop networks. IEEE Trans. Comput. 50 (2001), no. 5, 500--505.
• Mao, Jyh-Wen; Yang, Chang-Biau Shortest path routing and fault-tolerant routing on de Bruijn networks. Networks 35 (2000), no. 3, 207--215.
• Gu, Qian-Ping; Peng, Shietung Cluster fault-tolerant routing in star graphs. Networks 35 (2000), no. 1, 83--90.
• Liaw, Sheng-Chyang; Chang, Gerard J.; Cao, Feng; Hsu, D. Frank Fault-tolerant routing in circulant networks and cycle prefix networks. Ann. Comb. 2 (1998), no. 2, 165--172.
• Rescigno, A. A.; Vaccaro, U. Highly fault-tolerant routing in the star and hypercube interconnection networks. Parallel Process. Lett. 8 (1998), no. 2, 221--230.
• Gu, Qian-Ping; Peng, Shietung Node-to-set and set-to-set cluster fault tolerant routing in hypercubes. Parallel Comput. 24 (1998), no. 8, 1245--1261.
• Fàbrega, J.; Zaragozà, M. Fault-tolerant routings in double fixed-step networks. Discrete Appl. Math. 78 (1997), no. 1-3, 61--74.
• Gu, Qian-Ping; Peng, Shietung $k$-pairwise cluster fault tolerant routing in hypercubes. IEEE Trans. Comput. 46 (1997), no. 9, 1042--1049.
• Auletta, Vincenzo; Rescigno, Adele Anna; Scarano, Vittorio Fault tolerant routing in the supercube. Parallel Process. Lett. 3 (1993), no. 4, 393--405.
• Gargano, L.; Vaccaro, U.; Vozella, A. Fault tolerant routing in the star and pancake interconnection networks. Inform. Process. Lett. 45 (1993), no. 6, 315--320.
• Wada, Koichi; Luo, Yupin; Kawaguchi, Kimio Optimal fault-tolerant routings for connected graphs. Inform. Process. Lett. 41 (1992), no. 3, 169--174.
• Chen, Ming-Syan; Shin, Kang G. Depth-first search approach for fault-tolerant routing in hypercube multicomputers. IEEE Trans. Parallel Distrib. Systems 1 (1990), no. 2, 152--159.
• Chen, Ming-Syan; Shin, Kang G. Adaptive fault-tolerant routing in hypercube multicomputers. IEEE Trans. Comput. 39 (1990), no. 12, 1406--1416.
• (x) C. Hung, L.H. Hsu, and T.-Y. Sung, On the Construction of Combined k-Fault Tolerant Hamiltonian Graphs, Networks (2001), Vol 37 (3), pp. 165--170.

21. Some Problems on Optical Cross Connects and Optical MIN

• (x) Y. Yang, J. Wang and Y. Pan, ``Permutation capability of optical multistage interconnection networks,'' Journal of Parallel and Distributed Computing, vol. 60, no. 1, pp. 72-91, Jan. 2000.
• (xx) A. Rasala and G. Wilfong. Strictly nonblocking WDM cross-connects. In Proceedings of SODA, pages 606--615, 2000.