how to design the one-to-one communication algorithm between processors?

Question

Let me show you an example to specify my question. I have 4 processors 1-4. Any two of them have to do some communication. So in order to save time, we can proceed this as follows.

Time 1:(1,2)(3,4)
Time 2:(1,3)(2,4)
Time 3:(1,4)(2,3)

So we can see that for an even number n, we can finish this communication in n-1 times. But when the number of processors n becomes large, it is no easy thing to find an algorithm to make sure that each time there is no free processor.

If n equals 6. the following is not a good choice:

Time 1:(1,2)(3,4)(5,6)
Time 2:(1,3)(2,4) .... (5 and 6 have already communicated with each other, so they are free at time 2).

I have looked up many books about combinatorics even though my major is electromagnetics. but I still can not find answer. Can someone lead me in the right direction?

Answer 1

This problem is equivalent to edge coloring of the complete graph with even number of vertices. Each vertex corresponds to some "processor" and each color corresponds to "time" from the original problem.

Wikipedia article on edge coloring suggests a simple algorithm for this case:

place n points at the vertices and center of a regular (n − 1)-sided polygon. For each color class, include one edge from the center to one of the polygon vertices, and all of the perpendicular edges connecting pairs of polygon vertices.