Theoretical Computer Science / Theoretische Informatik

Institut[e] f(o|ü)r Informati(cs|k), [Universität] Osnabrück [University]

User Tools

Sidebar



External Links:

Table of Contents

Longest Induced Path

Here, you can find the benchmark sets used in our study of Longest Induced Path (LIP). Details can be found in:

Instances

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

File format of the instances

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

File format for the solutions

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.

research/lip.txt · Last modified: July 09, 2019 (21:39) by wiedera