forked from vardigroup/DPMC
-
Notifications
You must be signed in to change notification settings - Fork 1
/
README
35 lines (28 loc) · 1.27 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
This repository is primarily for PACE 2017 Track A submissions.
This repository contains both exact and heuristic submissions.
The exact algorithm implements the algorithm proposed in:
Tamaki, Hisao. "Positive-instance driven dynamic programming for treewidth."
arXiv preprint arXiv:1704.05286 (2017).
The heuristic algorithm starts with a greedy solution
and tries to improve the current solution
through local improvements. It looks at a
subtree of the current tree-decomposition around the largest bag and
runs the following decomposition algorithms on the
subgraph corresponding to this subtree in a round-robin manner:
the exact treewidth algorithm, an exact pathwidth algorithm,
and a heuristic (greedy) heuristic algorithm.
The final team members
Exact: Hisao Tamaki and Hiromu Ohtsuka
Heuristic: Hisao Tamaki, Hiromu Ohtsuka, Takuto Sato and Keitaro Makii
If you use the implementation provided in this repository in research work,
please cite the above paper and/or this repository in your publication reporting
the work.
Usage:
$ make exact
for making the exact submission
$ make heuristic
for making the heuristic submission, or
$ make
for making both
The commands are tw-exact and tw-heuristic as specified by the challenge rule.
These commands are implemented as shell scripts.