A connected graph where "layers" L₀ ... L_k partition the vertices. Each edge, which has a nonnegative integral weight, connects only vertices in successive layers. The width is the greatest number of vertices in any layer, i.e., MAX_i=0^k