
Software
Addibit is Another Double Description Implementation with BInary Trees. It supports the following adjacency test variants:
 combinatorial test using bit pattern trees [1,2] (bptrees),
 combinatorial test using bit pattern trees and query bits neutralization (bpqbntrees),
 combinatorial test using vantage point trees [3] (vptrees),
 algebraic test using the Gauss elimination method, and
 algebraic test using active set partitioning.
The current version is 0.3.0 (alpha) which may (and surely does) contain a lot of bugs.
Check the READMEfile for instructions of how to compile and run the program. For an overview of
the double description method, we refer to [4]. Here is a small study comparing the
performance of the different combinatorial test variants. The archive package contains statically compiled versions of the
noncommercial tools fourtitwo, cddr,
polco, porta,
ppl, skeleton and
lrs. Using the
script benchmark.sh, you can run addibit and the other tools on a set of arbitrary problems. Prepared problems can be found in the
archive (see folder experiments).
[1]

M. Terzer and J. Stelling.
Accelerating the computation of elementary modes using pattern trees.
In Proceedings of the 6th international conference on Algorithms
in Bioinformatics, WABI '06, pages 333343, Berlin/Heidelberg, 2006.
SpringerVerlag.
[ bib ]

[2]

M. Terzer and J. Stelling.
Largescale computation of elementary flux modes with bit pattern
trees.
Bioinformatics, 24:22292235, 2008.
[ bib ]

[3]

Peter N. Yianilos.
Data structures and algorithms for nearest neighbor search in general
metric spaces.
In Proceedings of the fourth annual ACMSIAM Symposium on
Discrete algorithms, SODA '93, pages 311321, Philadelphia, PA, USA, 1993.
Society for Industrial and Applied Mathematics.
[ bib ]

[4]

K. Fukuda and A. Prodon.
Double description method revisited.
In Combinatorics and Computer Science, volume 1120 of
Lecture Notes in Computer Science, pages 91111. SpringerVerlag,
Berlin/Heidelberg, 1996.
[ bib ]

Dipl.Inf. Blagoy Genov
Email: bgenov@informatik.unibremen.de

