TY - JOUR

T1 - Combinatorial problems related to origin-destination matrices

AU - Boros, Endre

AU - Hammer, Peter L.

AU - Ricca, Federica

AU - Simeone, Bruno

N1 - Funding Information:
The authors gratefully acknowledge the partial support by the Office of Naval Research (Grant N00014-92-J-1375), by the Italian Ministry of University and Research, by the Italian National Research Council, and by DIMACS, the National Science Foundation Center for Discrete Mathematics and Theoretical Computer Science at Rutgers University (NSF grant STC88-09648).

PY - 2001/11/15

Y1 - 2001/11/15

N2 - 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.

AB - 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.

KW - Generator

KW - Hamming space

KW - Origin-destination matrix

UR - http://www.scopus.com/inward/record.url?scp=0035980933&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0035980933&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(01)00212-8

DO - 10.1016/S0166-218X(01)00212-8

M3 - Article

AN - SCOPUS:0035980933

SN - 0166-218X

VL - 115

SP - 15

EP - 36

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -