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).
Select Git revision