NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
Combinatorial Analysis of Diagonal, Box and Greater-Than Polynomials as Packing Functions
Published
Author(s)
Pepe Torres Jimenez, Nelson Rangel-Valdez, Raghu N. Kacker, James F. Lawrence
Abstract
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.
Torres, P.
, Rangel-Valdez, N.
, Kacker, R.
and Lawrence, J.
(2015),
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 October 1, 2025)