Combinatorial problems related to origin-destination matrices

Endre Boros, Peter L. Hammer, Federica Ricca, Bruno Simeone

Research output: Contribution to journalArticlepeer-review


We consider the n-dimensional ternary Hamming space, Tn={0,1,2}n, and say that a subset L⊆Tn of three points form a line if they have exactly n-1 components in common. A subset of Tn 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 Tn. 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 origin-destination matrices in transportation systems.

Original languageEnglish (US)
Pages (from-to)15-36
Number of pages22
JournalDiscrete Applied Mathematics
Issue number1-3
StatePublished - Nov 15 2001

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


  • Generator
  • Hamming space
  • Origin-destination matrix


Dive into the research topics of 'Combinatorial problems related to origin-destination matrices'. Together they form a unique fingerprint.

Cite this