  This paper explores the application of a new algebraic method of edge
coloring, called complex coloring, to the scheduling problems of input queued
switches. The proposed distributed parallel scheduling algorithm possesses two
important features: optimality and rearrangeability. Optimality ensures that
the algorithm always returns a proper coloring with the minimum number of
required colors, and rearrangeability allows partially re-coloring the existing
connection patterns if the underlying graph only changes slightly. The running
time of the proposed scheduling algorithm is on the order of $O(\log^2 N)$ per
frame, and the amortized time complexity, the time to compute a matching per
timeslot, is only $O(\log N)$. The scheduling algorithm is highly robust in the
face of traffic fluctuations. Since the higher the variable density, the higher
the efficiency of the variable elimination process, complex coloring provides a
natural adaptive solution to non-uniform input traffic patterns. The proposed
scheduling algorithm for packet switching can achieve nearly 100% throughput.
