Combinatorial problems related to origindestination matrices
We consider the n-dimensional ternary Hamming space, , and say that a subset of three points form a line if they have exactly n?1 components in common. A subset of is called closed if, whenever it contains two points of a line, it contains also the third one. Finally, a generator is a subset, whose closure, the smallest closed set containing it, is . In this paper, we investigate several combinatorial properties of closed sets and generators, including the size of generators, and the complexity of generation. The present study was motivated by the problem of storing efficiently origindestination matrices in transportation systems.
hamming space generator origindestination matrix