Skip to content
No description, website, or topics provided.
Java C++ Python Other
Branch: master
Clone or download
Type Name Latest commit message Commit time
Failed to load latest commit information.
test_instance test instance folder and scripts for test added Mar 1, 2017
tw fixed memory bug May 24, 2017
LICENSE LICENSE file added May 1, 2017
Makefile bug in MainDecomposer fixed (disconnected case) Mar 1, 2017
README README revised for the final submission May 25, 2017
batch README edited Mar 1, 2017
tw-exact cr code removed Mar 1, 2017
tw-heuristic added tw.heuristic package May 15, 2017
validate test instance folder and scripts for test added Mar 1, 2017


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.

$ 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.

You can’t perform that action at this time.