Go back to Charles-Edmond Bichot's home page
Partitions found with the Fusion Fission method
This page presents new best solutions for the multi-way (also called k-way) graph partitioning problem. This solution have been produced by an application of the Fusion Fission method to the multi-way graph partitioning problem.
The Fusion Fission method
The Fusion Fission method is a new metaheuristic based on the physical nuclear process created by Charles-Edmond Bichot. The Fusion Fission method has been presented at IEEE International Parallel & Distributed Processing Symposium [Bic06] and more precisely described in the Journal of Mathematical Modelling and Algorithms [Bic07]. In these papers it is applied to the Normalized-Cut graph partitioning problem. Although the bases of the Fusion Fission method are presented in these papers, the metaheuristic framework of the Fusion Fission method has not yet been published.
This page presents results of the Fusion Fission method applied to the multi-way graph partitioning problem. Because the Normalized-Cut graph partitioning problem and the multi-way graph partitioning problem are very different, our application of Fusion Fission is quite new. At this time, there is no publication which presents the application of Fusion Fission to the multi-way graph partitioning problem.
The multi-way graph partitioning problem
Given an undirected graph G = G(V,E) of vertices V and edges E, a partition P_k of the set of vertices V into k parts is a set of k pairwise disjoints subsets of vertices such that there union is V. The k-way graph partitioning problem is to partition the vertices of G into k roughly equal parts, such that the number of edges connecting vertices in different parts is minimized.
The multi-way graph partitioning problem is a combinatorial optimization problem. The objective function to minimize is the edge-cut objective function which computes the sum of the edge-weights between parts. The constraint of the problem is to find a partition with roughly equal parts. For this purpose, the balance of a partition is used. It is defined as the maximum weight of a part of the partition, divided by the average weight of the parts. Then, if S_opt is the average weight of the parts and W the weight of the weightiest part of the partition P_k, the balance is : Bal(P_k)=W/S_opt.
Results of Fusion Fission compared with best results of 20 algorithms
The following tables summarize the best partitions found by the Fusion Fission method. These partitions are compared to those of the Graph Partitioning Archive maintained by Dr. Chris Walshaw of the University of Greenwich. Graph Partitioning Archive's partitions are the best partitions found by 20 state-of-the-art algorithms. Each partition found by Fusion Fission which had at least the same edge-cut than the corresponding partition of the Graph Partitioning Archive is underlined and can be downloaded. Each partition found by Fusion Fission which had a lower edge-cut than the corresponding partition of the Graph Partitioning Archive is in bold.
Depending on partitions balances, four tables present the comparison between best partitions found by Fusion Fission and best partitions found by the 20 algorithms of the Graph Partitioning Archive:
- To see the table I with a balance of 1.00, click here (a balance of 1.00 means that for each partition, its parts have the same weight).
- To see the table II with a balance of 1.01, click here.
- To see the table III with a balance of 1.03, click here.
- To see the table IV with a balance of 1.05, click here.
Table I:
A comparison between the best partitions found with the Fusion Fission algorithm and the partitions of the Graph Partitioning Archive. Balance = 1.00
Bal=1.00 |
k=2 |
k=4 |
k=8 |
Graph |
Algorithm |
Cut |
FF |
Algorithm |
Cut |
FF |
Algorithm |
Cut |
FF |
add20 |
PROBE |
596 |
671 |
JE |
1203 |
1207 |
iJ |
1758 |
1819 |
data |
PROBE |
189 |
193 |
iJ |
429 |
391 |
iJ |
728 |
728 |
3elt |
JE |
90 |
90 |
JE |
201 |
203 |
JE |
349 |
369 |
uk |
mpM4 |
20 |
20 |
JE |
44 |
44 |
JE |
91 |
99 |
add32 |
Ch2 |
11 |
11 |
pM4 |
37 |
34 |
JE |
75 |
72 |
bcsstk33 |
GCSVD |
10171 |
10171 |
iJ |
21956 |
22068 |
iJ |
35088 |
36862 |
whitaker3 |
JE |
127 |
127 |
JE |
382 |
388 |
JE |
664 |
713 |
crack |
JE |
184 |
184 |
JE |
368 |
370 |
JE |
687 |
721 |
wingnodal |
JE |
1707 |
1734 |
JE |
3581 |
3717 |
JE |
5443 |
5878 |
fe4elt2 |
MRSB |
130 |
130 |
JE |
349 |
351 |
JE |
617 |
638 |
vibrobox |
JE |
10343 |
11429 |
JE |
19245 |
19766 |
iJ |
25468 |
25903 |
bcsstk29 |
mpM4 |
2843 |
2843 |
MRSB |
8786 |
8603 |
iJ |
16832 |
17325 |
4elt |
JE |
139 |
139 |
JE |
327 |
338 |
JE |
556 |
612 |
fesphere |
JE |
386 |
386 |
NA |
773 |
793 |
JE |
1193 |
1289 |
cti |
JE |
334 |
334 |
JE |
977 |
963 |
JE |
1812 |
1947 |
memplus |
PROBE |
5513 |
5721 |
JE |
9754 |
9819 |
iJ |
12095 |
13110 |
cs4 |
JE |
372 |
411 |
JE |
964 |
1058 |
JE |
1496 |
1746 |
bcsstk30 |
JE |
6394 |
6394 |
JE |
16652 |
16837 |
JE |
34921 |
NA |
bcsstk31 |
PROBE |
2762 |
2782 |
iJ |
8322 |
7667 |
pM4 |
14426 |
15934 |
bcsstk32 |
JE |
4667 |
4890 |
JE |
10578 |
10247 |
JE |
22826 |
23537 |
t60k |
JE |
80 |
85 |
JE |
216 |
229 |
JE |
480 |
561 |
wing |
MQI |
791 |
925 |
JE |
1666 |
1859 |
JE |
2589 |
3018 |
brack2 |
JE |
731 |
731 |
JE |
3090 |
3154 |
JE |
7269 |
7844 |
finan512 |
Ch2 |
162 |
162 |
Ch2 |
324 |
324 |
Ch2 |
648 |
729 |
fetooth |
mpM4 |
3850 |
3951 |
iJ |
7605 |
7632 |
iJ |
12850 |
13084 |
ferotor |
PROBE |
2098 |
2135 |
Ch2 |
8097 |
7845 |
Ch2 |
14953 |
15712 |
598a |
PROBE |
2398 |
2437 |
Ch2 |
8379 |
8277 |
Ch2 |
17223 |
17276 |
feocean |
PROBE |
464 |
468 |
JE |
1923 |
1944 |
NA |
4760 |
5216 |
144 |
PROBE |
6490 |
6998 |
NA |
15964 |
16215 |
NA |
27751 |
28254 |
wave |
PROBE |
8692 |
8921 |
iJ |
18774 |
18070 |
iJ |
32204 |
32270 |
m14b |
MQI |
3836 |
3919 |
Ch2 |
14013 |
13597 |
pM4 |
28128 |
28714 |
|
Go back to the list of tables. Go back to the top of this page.
Table II:
A comparison between the best partitions found with the Fusion Fission algorithm and the partitions of the Graph Partitioning Archive. Balance = 1.01
Bal=1.01 |
k=2 |
k=4 |
k=8 |
Graph |
Algorithm |
Cut |
FF |
Algorithm |
Cut |
FF |
Algorithm |
Cut |
FF |
add20 |
GCSVD |
594 |
656 |
JE |
1203 |
1197 |
iJ |
1758 |
1800 |
data |
AMG |
188 |
189 |
iJ |
425 |
383 |
iJ |
719 |
693 |
3elt |
GrPart |
89 |
89 |
JE |
199 |
199 |
JE |
349 |
353 |
uk |
AMG |
19 |
19 |
JE |
44 |
43 |
JE |
86 |
96 |
add32 |
J2 |
10 |
10 |
JE |
33 |
33 |
JE |
69 |
66 |
bcsstk33 |
GrPart |
10109 |
10097 |
iJ |
21685 |
21662 |
iJ |
35088 |
35063 |
whitaker3 |
JE |
126 |
126 |
JE |
380 |
383 |
JE |
660 |
683 |
crack |
AMG |
183 |
183 |
JE |
368 |
367 |
NA |
678 |
707 |
wingnodal |
MQI |
1696 |
1704 |
JE |
3572 |
3628 |
JE |
5443 |
5747 |
fe4elt2 |
MRSB |
130 |
130 |
JE |
349 |
349 |
iJ |
611 |
630 |
vibrobox |
JE |
10310 |
11429 |
JE |
19245 |
19418 |
iJ |
25001 |
25604 |
bcsstk29 |
GrPart |
2818 |
2818 |
MRSB |
8786 |
8379 |
iJ |
16505 |
14926 |
4elt |
GrPart |
138 |
138 |
JE |
327 |
327 |
JE |
556 |
567 |
fesphere |
JE |
386 |
386 |
NA |
768 |
791 |
JE |
1152 |
1256 |
cti |
JE |
318 |
318 |
NA |
967 |
948 |
JE |
1812 |
1860 |
memplus |
JE |
5492 |
5663 |
JE |
9754 |
9792 |
iJ |
11939 |
12582 |
cs4 |
JE |
367 |
411 |
JE |
940 |
1043 |
NA |
1476 |
1693 |
bcsstk30 |
GrPart |
6335 |
6335 |
NA |
16622 |
16687 |
JE |
34604 |
35372 |
bcsstk31 |
GrPart |
2701 |
2703 |
pM4 |
7879 |
7554 |
pM4 |
14426 |
14193 |
bcsstk32 |
JE |
4667 |
4799 |
JE |
10578 |
9538 |
JE |
22826 |
23537 |
t60k |
AMG |
77 |
83 |
iJ |
213 |
225 |
NA |
467 |
506 |
wing |
MQI |
787 |
896 |
JE |
1666 |
1840 |
JE |
2589 |
3001 |
brack2 |
GrPart |
708 |
711 |
JE |
3090 |
3102 |
JE |
7269 |
7768 |
finan512 |
Ch2 |
162 |
162 |
Ch2 |
324 |
324 |
Ch2 |
648 |
648 |
fetooth |
SDP |
3823 |
3946 |
iJ |
7435 |
7433 |
iJ |
12850 |
12725 |
ferotor |
GrPart |
2049 |
2045 |
Ch2 |
8097 |
7795 |
iJ |
14028 |
13786 |
598a |
MQI |
2388 |
2423 |
NA |
8311 |
8222 |
iJ |
16594 |
17006 |
feocean |
GrPart |
387 |
391 |
NA |
1911 |
1878 |
NA |
4760 |
4538 |
144 |
MQI |
6479 |
6712 |
NA |
15345 |
16046 |
NA |
25818 |
27872 |
wave |
MQI |
8682 |
8855 |
iJ |
18058 |
17950 |
iJ |
32204 |
31965 |
m14b |
MQI |
3826 |
3902 |
JKM |
13844 |
13430 |
pM4 |
28128 |
27815 |
|
Go back to the list of tables. Go back to the top of this page.
Table III:
A comparison between the best partitions found with the Fusion Fission algorithm and the partitions of the Graph Partitioning Archive. Balance = 1.03
Bal=1.03 |
k=2 |
k=4 |
k=8 |
Graph |
Algorithm |
Cut |
FF |
Algorithm |
Cut |
FF |
Algorithm |
Cut |
FF |
add20 |
GCSVD |
576 |
647 |
JE |
1188 |
1187 |
iJ |
1720 |
1793 |
data |
AMG |
185 |
186 |
iJ |
383 |
380 |
iJ |
708 |
684 |
3elt |
JE |
87 |
87 |
JE |
199 |
199 |
JE |
336 |
341 |
uk |
JE |
18 |
18 |
JE |
41 |
43 |
JE |
82 |
94 |
add32 |
J2 |
10 |
10 |
JE |
33 |
33 |
JE |
69 |
66 |
bcsstk33 |
AMG |
10064 |
10064 |
iJ |
21423 |
21355 |
iJ |
34322 |
34940 |
whitaker3 |
JE |
126 |
126 |
JE |
380 |
381 |
JE |
658 |
677 |
crack |
AMG |
182 |
182 |
JE |
360 |
366 |
JE |
676 |
704 |
wingnodal |
SDP |
1680 |
1699 |
JE |
3566 |
3628 |
JE |
5401 |
5715 |
fe4elt2 |
MRSB |
130 |
130 |
JE |
349 |
349 |
JE |
603 |
630 |
vibrobox |
JE |
10310 |
11279 |
JE |
19245 |
19398 |
JE |
24874 |
25234 |
bcsstk29 |
GrPart |
2818 |
2818 |
J2 |
8541 |
8237 |
iJ |
16505 |
14868 |
4elt |
JE |
137 |
137 |
NA |
319 |
327 |
NA |
527 |
558 |
fesphere |
JE |
384 |
384 |
JE |
766 |
791 |
JE |
1152 |
1253 |
cti |
JE |
318 |
318 |
JE |
917 |
934 |
JE |
1716 |
1818 |
memplus |
JE |
5407 |
5574 |
JE |
9664 |
9710 |
iJ |
11939 |
12439 |
cs4 |
AMG |
362 |
404 |
JE |
936 |
1038 |
NA |
1472 |
1682 |
bcsstk30 |
JE |
6251 |
6251 |
JE |
16617 |
16588 |
JE |
34559 |
35299 |
bcsstk31 |
MLSATS |
2676 |
2686 |
pM4 |
7879 |
7440 |
pM4 |
14426 |
14008 |
bcsstk32 |
JE |
4667 |
4799 |
JE |
9728 |
9533 |
JE |
21307 |
23537 |
t60k |
AMG |
71 |
74 |
iJ |
211 |
216 |
NA |
467 |
496 |
wing |
MQI |
774 |
870 |
JE |
1636 |
1838 |
JE |
2551 |
3001 |
brack2 |
JE |
684 |
684 |
JE |
2864 |
2899 |
JE |
7080 |
7519 |
finan512 |
Ch2 |
162 |
162 |
Ch2 |
324 |
324 |
Ch2 |
648 |
648 |
fetooth |
SDP |
3792 |
3877 |
iJ |
7435 |
7404 |
iJ |
12850 |
12725 |
ferotor |
SDP |
1965 |
1966 |
Ch2 |
8097 |
7636 |
iJ |
14028 |
13588 |
598a |
MQI |
2367 |
2403 |
NA |
7978 |
8220 |
NA |
16031 |
17006 |
feocean |
GrPart |
311 |
312 |
NA |
1704 |
1856 |
NA |
4019 |
4538 |
144 |
MQI |
6438 |
6712 |
NA |
15250 |
16046 |
NA |
25611 |
27872 |
wave |
SDP |
8616 |
8851 |
iJ |
18058 |
17599 |
iJ |
30895 |
31311 |
m14b |
MQI |
3823 |
3882 |
JKM |
13844 |
13317 |
iJ |
27711 |
27815 |
|
Go back to the list of tables. Go back to the top of this page.
Table IV:
A comparison between the best partitions found with the Fusion Fission algorithm and the partitions of the Graph Partitioning Archive. Balance = 1.05
Bal=1.05 |
k=2 |
k=4 |
k=8 |
Graph |
Algorithm |
Cut |
FF |
Algorithm |
Cut |
FF |
Algorithm |
Cut |
FF |
add20 |
GCSVD |
550 |
633 |
iJ |
1184 |
1179 |
iJ |
1705 |
1783 |
data |
SDP |
181 |
184 |
iJ |
378 |
375 |
iJ |
702 |
669 |
3elt |
JE |
87 |
87 |
JE |
199 |
199 |
iJ |
334 |
343 |
uk |
JE |
18 |
18 |
JE |
41 |
41 |
JE |
82 |
93 |
add32 |
J2 |
10 |
10 |
JE |
33 |
33 |
JE |
69 |
65 |
bcsstk33 |
iJ |
9914 |
9914 |
iJ |
21229 |
21002 |
iJ |
34117 |
34686 |
whitaker3 |
JE |
126 |
126 |
JE |
380 |
381 |
JE |
658 |
677 |
crack |
AMG |
182 |
182 |
JE |
360 |
365 |
JE |
676 |
703 |
wingnodal |
SDP |
1668 |
1685 |
JE |
3566 |
3628 |
MLSATS |
5387 |
5687 |
fe4elt2 |
MRSB |
130 |
130 |
JE |
349 |
343 |
iJ |
597 |
625 |
vibrobox |
JE |
10310 |
11279 |
JE |
19245 |
19167 |
iJ |
24158 |
24894 |
bcsstk29 |
GrPart |
2818 |
2818 |
MLSATS |
8088 |
8148 |
MLSATS |
15314 |
14645 |
4elt |
JE |
137 |
137 |
NA |
319 |
325 |
NA |
527 |
551 |
fesphere |
JE |
384 |
384 |
JE |
766 |
791 |
JE |
1152 |
1253 |
cti |
JE |
318 |
318 |
JE |
917 |
897 |
JE |
1716 |
1787 |
memplus |
iJ |
5353 |
5392 |
MLSATS |
9427 |
9453 |
iJ |
11939 |
12316 |
cs4 |
AMG |
356 |
383 |
JE |
936 |
1038 |
NA |
1472 |
1682 |
bcsstk30 |
JE |
6251 |
6251 |
JE |
16617 |
16438 |
JE |
34559 |
34806 |
bcsstk31 |
MLSATS |
2676 |
2686 |
pM4 |
7879 |
7399 |
iJ |
13561 |
13950 |
bcsstk32 |
JE |
4667 |
4695 |
JE |
9728 |
9052 |
JE |
21307 |
23202 |
t60k |
SDP |
65 |
67 |
iJ |
211 |
211 |
NA |
467 |
496 |
wing |
MQI |
770 |
870 |
JE |
1636 |
1838 |
JE |
2551 |
3001 |
brack2 |
SDP |
660 |
660 |
MLSATS |
2808 |
2755 |
JE |
7080 |
7505 |
finan512 |
Ch2 |
162 |
162 |
Ch2 |
324 |
324 |
Ch2 |
648 |
648 |
fetooth |
SDP |
3773 |
3877 |
MLSATS |
7152 |
7404 |
iJ |
12646 |
12725 |
ferotor |
SDP |
1957 |
1966 |
Ch2 |
8097 |
7520 |
iJ |
13184 |
13588 |
598a |
MQI |
2336 |
2366 |
NA |
7978 |
8195 |
NA |
16031 |
16942 |
feocean |
GrPart |
311 |
312 |
NA |
1704 |
1822 |
NA |
4019 |
4433 |
144 |
SDP |
6362 |
6689 |
NA |
15250 |
16046 |
NA |
25611 |
27872 |
wave |
MQI |
8563 |
8777 |
iJ |
18058 |
17320 |
MLSATS |
30583 |
31207 |
m14b |
MQI |
3802 |
3878 |
JKM |
13844 |
13317 |
iJ |
27711 |
27815 |
|
Go back to the list of tables. Go back to the top of this page.
Go back to Charles-Edmond Bichot's home page
Last Update: 2007-07-12