The equicut problem in a graph with 2n nodes asks for a smallest cut with shores of size n.

[Example Graph]

As an example, the red edges in the above picture rapresent minimum equicuts of the two graphs.


Before using our tool you must encode in DIMACS format your graph. As an example, the first graph in the above picture must be encoded as follows.
The first character of each line describes the information given by the line:

c The following lines are all comments
c number of vertices  : 6
c nonisolated vertices: 6
c number of edges     : 8
c This is the last comment line
p gp 6 8
e 1 2
e 1 3
e 2 3
e 2 4
e 3 5
e 4 5
e 4 6
e 5 6

WARNING: The nodes must be numbered from 1 to no. of nodes.


The above file must be saved in your local machine and then submitted to our solver by typing its name in the appropriate input field.

When you start the solver by pressing the apposite button, your file is transferred to our machine over the Internet. At this point our heuristic is executed and, after a certain waiting time, the best equicut found during the entire search is returned to you. Finally, all intermediate data, including your input file, are discarded from our server.

Feedback from the users is most welcome.

© 2005-2009 Roberto Battiti and Mauro Brunato, All Rights Reserved.
Pages hosted by "machine Learning and Intelligent Optimization (LION)" Group - DISI - Università di Trento - Italy.
Last updated: 2012-03-15 07:05:40