Schedules in {0,1}n (Open)

Summary: It is desired to find the distribution of cycle lengths in a certain family of digraphs. The nth graph in this family has vertex set {0,1}n, and (u,v) belongs to the edge set if and only if v can be obtained from u by (i) changing the first coordinate from 0 to 1, (ii) changing the nth coordinate from 1 to 0, or (iii) changing a consecutive pair from (1,0) to (0,1). A first step would be to determine or estimate the length of the longest cycle in such a graph. This problem arises in connection with multichamber tools for IC manufacturing.

Classification: Primary, discrete mathematics; Secondary, graph theory

• Download Problem [PDF]

Donate · Contact Us · Site Map · Join SIAM · My Account