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

pace-2020

    • Name Last commit Last update
    ..
    CMakeLists.txt
    Makefile
    README.txt
    components.c
    components.h
    compression.c
    compression.h
    decompose.c
    decompose.h
    graph.c
    graph.h
    heap.c
    heap.h
    lire.c
    lire.h
    lists.c
    lists.h
    main.c
    main.h
    separator.c
    separator.h
    sets.c
    sets.h
    swaps.c
    swaps.h
    tree.c
    tree.h
    utils.c
    utils.h
    README.txt
    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).