Skip to content
Snippets Groups Projects
Select Git revision
  • master
1 result

pace-2020

  • 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).