treedepth : A program that builds a tree decomposition of a graph.
The approach consists first in decomposing recursively the graph, searching each time a partition A|B|C of the vertices such that there is no edge of G whose extremities are one in A and the other in B. C is the separator.
The resulting decomposition is improved applying pullups and ejections while the height of the decomposition decreases.
Type make to build the program named treedepth. Type ./treedepth -help to print usage information.
For example ./treedepth -file heur_111.gr time 60.
Use make PACE=yes to generate a version of the program corresponding to pace 2020 requirements (no options in line then).
DOI 10.5281/zenodo.3884054