This package contains the source and the test data for a solver for
the Highly Connected Deletion problem. It is described in the paper:
Falk Hüffner, Christian Komusiewicz, Adrian Liebtrau, and
Rolf Niedermeier:
Partitioning Networks into Highly Connected Clusters with Maximum
Edge Coverage
Manuscript, 2012.
The Highly Connected Deletion problem is, given a graph, to delete a
minimum number of edges such that each remaining connected component
is highly connected. Here, a graph with n vertices is highly connected
if more than n/2 edges need to be deleted to make it disconnected, or
equivalently each vertex has degree larger than n/2.
The current version can be obtained at
http://www.user.tu-berlin.de/hueffner/hcd. It is distributed under the
terms of the GNU General Public License (GPL); either version 2 (see
COPYING), or (at your option) any later version. It uses the min-cut
routines by Chandra Chekuri, Andrew Goldberg, David Karger, Matthew
Levine, and Cliff Stein (see mincut/README).
The solver is written in Objective Caml and C++. To build the
program, you need
* Objective Caml (version 3.10 or newer)
* the GNU gcc compiler (version 3.4 or newer)
* GNU make
* CPLEX 12.3 or newer.
Using other compilers or makes, building on a non-Unix system, or
compiling without CPLEX support will require changes to the Makefile
and the source.
It has been tested on:
* Debian GNU/Linux (amd64) 7 with Objective Caml 3.12.1, gcc 4.7.1
(Debian 4.7.1-7), and CPLEX 12.4.
To build, type make in the mincut directory and then make in the main
directory.
Highly Connected Deletion solver
================================
The program is called "hcd". It reads a graph from standard input and
writes it to standard output (note that on Unix systems, you can close
standard input from the keyboard with Control-d). The graph format is
a simple text format, where each line describes one edge. Edges are
given by two vertex lables divided by whitespace. Comment text
starting with '#' will be ignored up to the next newline. Example:
# graph
v0 v1
v1 v2
v2 v0
Vertex names can be any combination of letters, digits, and _.
The output is a minimum set of edges to delete to make every remaining
connected component highly connected. Example:
$ ./hcd < BB11001.graph
3_33 0_35
0_34 3_32
1_62 2_75
2_90 3_80
0_74 1_69
[...]
A list of options can be obtained with
./hcd --help
Data
====
The directory "data" contains the test instances and clusters found as
described in the paper.
Version history
===============
1.0 2012-10-16 initial release
-- Falk Hüffner (http://www.user.tu-berlin.de/hueffner/)