The equicut problem in a graph with 2n nodes asks
for a smallest cut with shores of size n.
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` begins a comment line;
- `e` describes a single edge (in the example below the endnodes of the last edge are 5 and 6);
- `p` starts the problem line. The two numbers into the problem line are no. of nodes and no. of edges respectively. The string `gp` into the problem line states that this is a Graph Partitioning problem. The problem line must preceed any edge declaration.
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.
Pages hosted by "machine Learning and Intelligent Optimization (LION)" Group - DISI - Università di Trento - Italy.
Last updated: 2012-03-15 07:05:40
![[Reactive Search Logo]](images/logo.jpg)
