Groupe d’études et de recherche en analyse des décisions

G-93-28

Coding Chemical Trees with the Centered N-Tuple Code

, , et

We propose a new coding algorithm (called NTUPLE) for computing the N-tuple code (due to Knop et al.) for chemical trees. The algorithm NTUPLE has a time complexity in O (N), where N is the number of verticesof the tree instance, on a RAM machine and a time complexity in O (N2) on a machine with words of bounded length. We also introduce a variant of the N-tuple code, which we call the Centered N-tuple code, and provide a coding algorithm (called CENTERTUPLE) to compute it. The algorithm CENTERTUPLE has a time complexity in O (N) on a RAM machine and in O (N log N) on a machine with words of bounded length. C implementations of both coding algorithms are included.

, 39 pages