2003/01/24 by Lauro Lins, Sóstenes Lins, Lins, Lauro +5
Computer Science · Engineering · #Algorithms and Data Compression #Optimization and Packing Problems #cs.DM #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.cs/0301025
12 pages, 4 figures
arxiv created 2003/01/24 · arxiv updated 2009/11/30
In this paper we propose a simple and efficient strategy to obtain a data structure generator to accomplish a perfect hash of quite general order restricted multidimensional arrays named \em phormas. The constructor of such objects gets two parameters as input: an n-vector a of non negative integers and a boolean function B on the types of order restrictions on the coordinates of the valid n-vectors bounded by a. At compiler time, the phorma constructor builds, from the pair a,B, a digraph G(a,B) with a single source s and a single sink t such that the st-paths are in 1-1 correspondence with the members of the B-restricted a-bounded array A(a,B). Besides perfectly hashing A(a,B), G(a,B) is an instance of an NW-family. This permits other useful computational tasks on it.