Combinatorial Analysis of Diagonal, Box and Greater-Than Polynomials as Packing Functions
Pepe Torres Jimenez, Nelson Rangel-Valdez, Raghu N. Kacker, James F. Lawrence
Packing functions (PFs) are bijections between a set of m-dimensional vectors V over Nm and nonnegative integers N. PFs have several applications, e.g. in partitioning schemes or text compression. Two important categories of PFs are diagonal polynomials (DP), and box polynomials (BP). The bijections of DP and BP have mostly been addressed for small dimensions. We discuss a bijection, called greater-than polynomials (or GTP), between restricted m- dimensional vectors over Nm and N. Also, we discuss direct and inverse methods for DP, GTP and BP of any dimension m. These methods are compared in terms of their computational complexity. The analysis reveals that BP is an efficient PF because its direct and inverse methods required O(n2 * m) and O(n3 * m) bit operations, respectively; here n is least upper bound of log2 α and α belongs to N. Finally, we present an interesting relationship between GTP, DP and a special case of Diophantine equations.
, Rangel-Valdez, N.
, Kacker, R.
and Lawrence, J.
Combinatorial Analysis of Diagonal, Box and Greater-Than Polynomials as Packing Functions, Applied Mathematics & Information Sciences, [online], https://doi.org/10.12785/amis/090601
(Accessed December 5, 2023)