Combinatorial Analysis of Diagonal, Box and Greater-Than Polynomials as Packing Functions

Published

November 1, 2015

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 N^m 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 N^m 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(n² * m) and O(n³ * m) bit operations, respectively; here n is least upper bound of log₂ α 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

Pub Type

Journals

Download Paper

https://doi.org/10.12785/amis/090601

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 September 19, 2024)