




Combinatorial Analysis of Diagonal, Box, and GreaterThan Polynomials as Packing Functions 

PP: 27572766 

Author(s) 

Jose TorresJimenez,
Nelson RangelValdez,
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 GreaterThan Polynomial between restricted m−dimensional vectors over Nm and N. We give details of two interesting
applications of packing functions: (a) the application of greaterthan polynomials for the manipulation of Covering Arrays that are
used in combinatorial interaction testing; and (b) the relationship between graterthan and diagonal polynomials with a special case of
Diophantine equations. A comparison of the bijections for box, diagonal and greaterthan 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) 




