From koc@ECE.ORST.EDU Mon Nov 8 17:03:07 1999 Date: Mon, 08 Nov 1999 17:02:33 -0800 From: Cetin Kaya Koc To: ISLMAIL Subject: 11/10/99 - Department of Computer Science Colloquium Computer Science Colloquium Dr. Bella Bose Dept. of Computer Science Oregon State University Owen (ECE) 101 3:00 pm Wednesday, November 10, 1999 TITLE: Gray Codes and Edge Disjoint Hamiltonian Cycles in Torus ABSTRACT: Many commercial parallel systems have been built with torus as the processor interconnection topology. Lee distance is an appropriate metric useful to describe the interconnection topology of these toroidal networks. Many topological properties of these networks can be developed based on Lee distance. In this talk, we concentrate on edge disjoint Hamiltonian cycles. First we present our results on Lee distance Gray codes and then show how these codes can be used to generate edge disjoint Hamiltonian cycles in torus. These results are also extended to hypercubes. We also describe methods of generating edge disjoint Hamiltonian cycles in De Bruijn networks. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Debbie Shannon Oregon State University Computer Science Department 303 Dearborn Hall Corvallis, OR 97331-3202 debbie@cs.orst.edu Phone: 541-737-5556 Fax: 541-737-3014