@article{oai:ipsj.ixsq.nii.ac.jp:00219082,
 author = {Kenji, Kanazawa and Kenji, Kanazawa},
 issue = {1},
 journal = {情報処理学会論文誌コンピューティングシステム（ACS）},
 month = {Jul},
 note = {The Swap-Based Tabu Search (SBTS) is a heuristic algorithm for solving the maximum independent set problems and can solve the maximum clique problems as well because the maximum clique in a graph is equivalent to the maximum independent set in its complementary graph. Although SBTS is a powerful algorithm in solving the maximum clique problems and has abundant inherent parallelism, it is difficult to parallelize because of its solution searching heuristic involving indirect indexing on array components. In this paper, we show a variant of SBTS that does not require indirect indexing while maintaining the same accuracy as that of the original version of SBTS and describe its hardware acceleration using a Field-Programmable Gate Array (FPGA). Experimental results show that our proposed SBTS variant on FPGA can solve the maximum clique problems up to 51.1 times faster than the original SBTS algorithm on CPU and up to 5.40 times faster than our proposed SBTS variant on CPU, respectively.
------------------------------
This is a preprint of an article intended for publication Journal of
Information Processing(JIP). This preprint should not be cited. This
article should be cited as: Journal of Information Processing Vol.30(2022) (online)
------------------------------, The Swap-Based Tabu Search (SBTS) is a heuristic algorithm for solving the maximum independent set problems and can solve the maximum clique problems as well because the maximum clique in a graph is equivalent to the maximum independent set in its complementary graph. Although SBTS is a powerful algorithm in solving the maximum clique problems and has abundant inherent parallelism, it is difficult to parallelize because of its solution searching heuristic involving indirect indexing on array components. In this paper, we show a variant of SBTS that does not require indirect indexing while maintaining the same accuracy as that of the original version of SBTS and describe its hardware acceleration using a Field-Programmable Gate Array (FPGA). Experimental results show that our proposed SBTS variant on FPGA can solve the maximum clique problems up to 51.1 times faster than the original SBTS algorithm on CPU and up to 5.40 times faster than our proposed SBTS variant on CPU, respectively.
------------------------------
This is a preprint of an article intended for publication Journal of
Information Processing(JIP). This preprint should not be cited. This
article should be cited as: Journal of Information Processing Vol.30(2022) (online)
------------------------------},
 title = {FPGA Acceleration of Swap-Based Tabu Search for Solving Maximum Clique Problems},
 volume = {15},
 year = {2022}
}