chapter  14
16 Pages

A Dynamic Location Problem

This chapter develops a graph invariant called windex, introduced by Chung, Graham, and Saks (1987, 1989) in the context of dynamic location theory. It is closely connected to Cartesian products of complete graphs. These graphs, known as Hamming graphs, are treated in the first section, while the second section introduces the dynamic location problem and the corresponding invariant windex. Then quasi-median graphs are introduced as a natural generalization of median graphs. The chapter culminates with a proof that graphs with finite windex coincide with quasi-median graphs.