External Links:
Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]
Here, you can find the benchmark sets used in our study of Longest Induced Path (LIP). Details can be found in:
Type | Description | Filename | Solutions |
---|---|---|---|
MG | moviegalaxies | lip_mg.tar.bz2 | results_mg.csv |
CRN | Real world networks | lip_crn.tar.bz2 | results_crn.csv |
BAL | Barabasi-Albert graphs with 100 nodes | lip_bal.tar.bz2 | results_bal.csv |
BAS | Barabasi-Albert graphs with 20-40 nodes | lip_bas.tar.bz2 | results_bas.csv |
The tar.bz2-files contain plain text files in the graphml format, where each graphml file contains a single instance. The naming scheme for these files is as follows:
Moviegalaxy instances: <movie title>.graphml Realworld instances: <name>.graphml Barabasi-Albert: ba.<#nodes>.<density>.<instance number>.graphml
The solution files are plain text files in the CSV format with a comma as the delimiter. The first line of a file serves as a column header. Each further line represents a specific instance. The column headers are as follows:
Header | Description |
---|---|
filename | the filename of the specific instance |
#n | the number of nodes |
#m | the number of edges |
OPT | the optimal solution or -1 if none was found |
Walk RT | the runtime of ILP_Walk in seconds |
Walk OPT | the best solution found by ILP_Walk |
Flow RT | the runtime of ILP_Flow in seconds |
Flow OPT | the best solution found by ILP_Flow |
C_[n,c]_(int|frac) RT | the runtime of ILP_Cut in seconds |
C_[n,c]_(int|frac) OPT | the best solution found by ILP_Cut |
We tested 8 configurations of ILP_Cut. For each there are two columns. The naming scheme of the configurations is the same as in the paper: n
indicates that the edge variables are relaxed and node variables are added; c
that clique constraints for a heuristically found set of disjoint cliques were added before solving the ILP. int
or—otherwise—frac
indicate that the separation uses only integral or also fractional solutions, respectively.