README.txt 714 Bytes
Newer Older
stephgc's avatar
stephgc committed
1
2
3
4
5
6
7
8
9
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).

Stephane Grandcolas's avatar
Stephane Grandcolas committed
10
11
DOI 10.5281/zenodo.3884054