TCS-Meiji
Folders and files
Name | Name | Last commit date | ||
---|---|---|---|---|
parent directory.. | ||||
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.