Abstract | ||
---|---|---|
Consider sets S of hypercubes of side 2 in the discrete n-dimensional torus of side 4 with the property that every possible hypercube of side 2 has a nonempty intersection with some hypercube in S. The problem of minimizing the size of S is studied in two settings, depending on whether intersections between hypercubes in S are allowed or not. If intersections are not allowed, then one is asking for the smallest size of a non-extensible packing S; this size is denoted by f(n). If intersections are allowed, then the structure S is called a blocking set. The smallest size of a blocking set S is denoted by h(n). By computer-aided techniques, it is shown that f(5)=12, f(6)=16, h(6)=15 and h(7)≤23. Also, non-extensible packings as well as blocking sets of certain small sizes are classified for n≤6. There is a direct connection between these problems and a covering problem originating from the football pools. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1016/j.ipl.2014.08.005 | Information Processing Letters |
Keywords | Field | DocType |
Combinatorial problems,Computational geometry,Blocking set,Covering,Non-extensible packing | Discrete mathematics,Blocking set,Combinatorics,Computational geometry,Torus,Mathematics,Hypercube | Journal |
Volume | Issue | ISSN |
115 | 2 | 0020-0190 |
Citations | PageRank | References |
1 | 0.35 | 8 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
K. Ashik Mathew | 1 | 12 | 1.75 |
Patric R. J. Östergård | 2 | 609 | 70.61 |