No description, website, or topics provided.
Switch branches/tags
Nothing to show
Clone or download
Latest commit 552341d May 25, 2017
Permalink
Failed to load latest commit information.
gala update May 24, 2017
tdlib final submission May 25, 2017
Makefile final submission May 25, 2017
README final submission May 25, 2017
tw-exact update May 24, 2017
tw-heuristic update May 24, 2017

README

CONTENTS

PACE17/A [1] submission -- tdlib/experimental and gala snapshot

USAGE/SYNOPSIS

"make" should build everything needed to run ./tw-exact and ./tw-heuristic.

these programs read a ".gr" file from stdin, and print a ".td" file to stdout.
./tw-exact terminates after finish, ./tw-heuristic will wait for a TERM
signal. -L -D -T flags switches on logging/debugging/tracing.

TW-EXACT

is basically Hisao Tamakis implementation that won last year. It has been ported
to C++11 and boost/gala/tdlib. It is now ran after the tdlib preprocessor. The
development has been discontinued in favor of tw-heuristic.

TW-HEURISTIC

Performs rule based Preprocessing followed by an exaustive but guided brute
force search over elimination orderings. Lower bounds computed by
deltaC_leastC are used to cut off branches. minimalChordal is used to refine
orderings.

EXAMPLE

$ make
[..]
$ ./tw-exact < tdlib/grtd/HoffmanGraph.gr
[..]
$ ./tw-heuristic < tdlib/grtd/HoffmanGraph.gr & p=$!; sleep 1; kill $p

BUGS

signal handling
- too early TERM might not be handled right.
- reaction to TERM may be late.

package
the embedded tdlib package is incomplete and experimental. the proposed
algorithms, subroutines and executables will be made fully available in a
future version of tdlib.

REFERENCES

[1] https://pacechallenge.wordpress.com/pace-2017/track-a-treewidth/