3-Terminal Steiner Tree (3TST) is a heuristic for the Steiner tree problem. Intuitively, the heuristic works by replacing 3-terminal subtrees of a prospective solution with lighter 3-terminal subtrees. This process is repeated until no significant improvement is observed in a reasonable amount of time.
Open a windows/linux terminal and execute the following command to clone this repository.
git clone https://github.com/AutoProving/3TST.git
Enter the main folder 3TST
and type make
to compile the program.
An executable called 3TST.exe
will be created.
The simplest way of executing the program is to run the following command.
It will read the input graph from the standard input and print a Steiner tree
on the standard output. This is a deterministic procedure. It can be stopped
manually using a SIGINT
or a SIGTERM
.
./3TST.exe < examples/instance1.gr
The timeout
command can be used to run it with a time limit.
timeout -s TERM 10s ./3TST.exe < examples/instance1.gr
The option -h
or --help
prints the help message
./3TST.exe --help
The option -r
or --random
enables the use of a randomised procedure. This option makes
the program run until it receives a SIGTERM or SIGINT otherwise it will never stop.
In this case the timeout
command is useful.
timeout -s TERM 90s ./3TST.exe --random < examples/instance1.gr
It is possible to give a specific seed to initialise the random number generator using
the flag -s
or --seed
. This flag have effect only with the --random
option.
In the example below, the seed is 10.
./3TST.exe -r -s 10 < examples/instance1.gr
With the option -i
or --improve
we can execute the program on a graph instance
together with an initial Steiner tree. In this case, the program will try to improve
the Steiner tree. This is a deterministic procedure. --random
and
--seed
have no effect with --improve
.
cat examples/instance1.gr examples/steinertree1.ost | ./3TST.exe -i
The input format for graphs and the output format for Steiner trees are the same used at PACE Challenge 2018. Please refer to the file INPUT_OUTPUT.md for a description of these formats. Alternatively, please read Sections A and B of the following link:
https://pacechallenge.org/2018/steiner-tree/
The examples
folder contains some examples from the PACE Challenge.
Please report bugs or ask questions using the issue tracker a https://github.com/AutoProving/3TST/issues
To cite our heuristics, please refer to the following paper.
Emmanuel Arrighi, Mateus de Oliveira Oliveira. Three is Enough for Steiner Trees. 19th Symposium on Experimental Algorithms.
Emmanuel Arrighi acknowledges support from the Research Council of Norway in the context of the project Parameterized Complexity for Practical Computing (Grant no. 274526)
Mateus de Oliveira Oliveira acknowledges support from the Research Council of Norway in the context of the project Automated Theorem Proving from the Mindset of Parameterized Complexity Theory (Grant no. 288761).
We also acknowledge support from the Sigma2 Network (Proj. no. NN9535K)