MinCut Results

Minimum Cut Instances

Computational Results

Problem	n	cost of min cut	nodes on t-side of optimal cut	separation steps req'd by
Problem	n	cost of min cut	nodes on t-side of optimal cut	NEW	NEWJ
mincut100p1-1	100	1	any	1865	7
mincut100p1-1	100	1	any	1865	7
mincut100p1-2	100	1	any	1751	8
mincut100p1-3	100	1	any	1883	11
mincut100p1-4	100	1	any	2069	9
mincut100p1-5	100	1	any	1794	6
mincut100p1-1L	100	1203	98	248	4
mincut100p1-2L	100	1223	96	268	5
mincut100p1-3L	100	1160	98	202	5
mincut100p1-4L	100	1119	2	193	4
mincut100p1-5L	100	1093	2	208	4
mincut100p1-1D	100	1157	98	194	5
mincut100p1-2D	100	1039	2	134	4
mincut100p1-3D	100	1259	2	232	4
mincut100p1-4D	100	1140	2	186	6
mincut100p1-5D	100	1089	2	193	4
mincut100p1-1K	100	2958	98	178	5
mincut100p1-2K	100	3000	98	193	5
mincut100p1-3K	100	2902	98	184	5
mincut100p1-4K	100	2955	98	198	5
mincut100p1-5K	100	2922	2	184	5
mincut100p10-1	100	10	any	890	6
mincut100p10-2	100	10	any	1006	5
mincut100p10-3	100	10	any	1338	5
mincut100p10-4	100	10	any	>5000*	5
mincut100p10-5	100	10	any	>5000*	6
mincut100p10-1L	100	10679	87	1148	7
mincut100p10-2L	100	10660	12	1071	6
mincut100p10-3L	100	10522	13	857	6
mincut100p10-4L	100	10600	16	1399	6
mincut100p10-5L	100	10705	85	1034	6
mincut100p10-1D	100	10746	12 or 16	1034	8
mincut100p10-2D	100	10937	87	925	6
mincut100p10-3D	100	10639	88	988	5
mincut100p10-4D	100	10844	12	955	6
mincut100p10-5D	100	10439	15	903	6
mincut100p10-1K	100	19724	89	302	6
mincut100p10-2K	100	19456	11	324	6
mincut100p10-3K	100	19598	11	344	6
mincut100p10-4K	100	19506	11	314	6
mincut100p10-5K	100	19314	89	300	6

*algorithm did not terminate within 5000 separations.

Many helpful discussions contributed to this paper.
Special thanks goes to Dave Gay and R. Ravi