Skip to main content
U.S. flag

An official website of the United States government

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.
Citation
Applied Mathematics & Information Sciences
Volume
9
Issue
6

Keywords

Diagonal Polynomials, Box Polynomials, Greater-Than Polynomials

Citation

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 March 29, 2024)
Created November 1, 2015, Updated June 2, 2021