|
|
 |
| |
|
|
|
Combinatorial Analysis of Diagonal, Box, and Greater-Than Polynomials as Packing Functions |
|
|
|
PP: 2757-2766 |
|
|
|
Author(s) |
|
|
|
Jose Torres-Jimenez,
Nelson Rangel-Valdez,
Raghu N. Kacker,
James F. Lawrence,
|
|
|
|
Abstract |
|
|
| A packing function is a bijection between a subset V ⊆ Nm and N, where N denotes the set of non negative integers N.
Packing functions have several applications, e.g. in partitioning schemes and in text compression. Two categories of packing functions
are Diagonal Polynomials and Box Polynomials. The bijections for diagonal ad box polynomials have mostly been studied for small
values of m. In addition to presenting bijections for box and diagonal polynomials for any value of m, we present a bijection using
what we call Greater-Than Polynomial between restricted m−dimensional vectors over Nm and N. We give details of two interesting
applications of packing functions: (a) the application of greater-than polynomials for the manipulation of Covering Arrays that are
used in combinatorial interaction testing; and (b) the relationship between grater-than and diagonal polynomials with a special case of
Diophantine equations. A comparison of the bijections for box, diagonal and greater-than polynomials are presented and we conclude
that the bijection for box polynomials is efficient because its direct and inverse methods have orders of O(n2 ·m) and O(n3 ·m) (measured
in terms of bit operations, where n is the number of bits of an integer involved in the methods) |
|
|
|
|
|
|
|
