With QuasiDec one can compute the block decomposition of a quasi-median graph obtained from a set of partitions or a sequence alignment.


The computation works without computing the quasi-median graph itself and runs in time polynomial in input and output, as described in detail in the paper "Computing cut vertices in quasi-median graphs" by Herrmann and Moulton.


The software is implemented in C++ as an extension of the software system polymake. You must download and install polymake (version 2.12) before you can use QuasiDec. Then, download our extensions and extract it, start polymake and run 'import_extension DIR;' where DIR is the directory you extracted the file to (This may take some time as polymake will then compile the extension for you). For more information go to polymake extensions. You need to satisfy all prerequisites for polymake to install our software.

QuasiDec is copyright (c) Sven Herrmann and is freely available under the GNU General Public License. polymake operates under the same licence.

If you use QuasiDec, please cite the reference below.


QuasiDec Documentation


For technical questions or feature requests, e-mail Dr. Sven Herrmann.


S. Herrmann and V. Moulton, Computing cut vertices in quasi-median graphs, 2012.

Research Team

Dr.Sven HerrmannProf.Vincent Moulton