Download Apptopinv User's Guide

It is possible to check whether the input graph is planar or outerplanar by
using the following parameters instead of supported problems:
• -planar to test planarity, and
• -oplanar to test outerplanarity.
Here is an example to test the outerplanarity of a graph:
./a.out 1 rest.txt -oplanar -no -no -f graphs/data/g3.dat
The problem type is -planar or -oplanar. Algorithm type is set -no and
simulated annealing is set -no. Graph source options can be used normally (see
the following sections for details). The result file and number of repeats are
still needed in the parameter list. Planarity test is performed only once, and no
information about the run is written in the result file (modify file appropinv.cpp,
if you like to change this).
Basically, it is possible to add other optimization problems, but depending
on your problem, there might be more or less difficulties. These four problems
are very similar, although in problems MPS and MOPS we try to maximize and
in problems TH and OTH the aim is to minimize the solutions.
3.3
Different algorithms and solution optimization
Next we describe the use of different algorithms. In Table 3.1 there is a list of
heuristics that can be used with different problems. We have also listed references for the origin of the algorithm and reported experiments. Also some remarks on the running time (time) and relative performance (sol’n) of algorithms
are reported. There might be graphs for which the suggestions are completely
wrong.
Table 3.1: Supported algorithm and problem types.
Algorithm
-g -sa/-no
-ca -sa/-no
-gca -sa/-no
-ca1 -sa/-no
-gca1 -sa/-no
-ca2 -sa/-no
-gca2 -sa/-no
-ht -sa/-no
-st -sa/-no
-e -sa
MPS
MOPS
TH
OTH
time
sol’s
references
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
slow
fast
slow
fast
slow
fast
slow
slow
fast
slow
average/poor
good
good
very good
good/best
good?
good?/average
good
poor
average/good
[8, 29]
[7, 29, 30]
[29, 29, 30]
[31, 29, 30]
[29]
[31, 30]
[30]
[21, 25, 26, 8, 9]
[10, 30]
[28, 32, 29]
x
x
x
x
x
After you choose an algorithm to get initial solution, you have to decide
whether you try to optimize your solution with simulated annealing (-sa / -no).
Usually simulated annealing (SA) improves the solutions (this depends of course
8