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

pace-2020

  • Clone with SSH
  • Clone with HTTPS
    • user avatar
    pace 2020 version
    stephgc authored
    348f3ab0
    History
    user avatar 348f3ab0
    History
    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
    sga: a program that constructs a tree decomposition of a graph.

The approach consists first in performing recursively decompositions of the graph, building ta partition of the vertices A-B-C such that there are no edge of G between vertices of A and B. C is the separator. 
Then the resulting decomposition is improved applying pullup and swap operations 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.