The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm
Let <inline-formula><math display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inl...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-10-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/13/10/253 |
| _version_ | 1797551800099799040 |
|---|---|
| author | Derek H. Smith Roberto Montemanni Stephanie Perkins |
| author_facet | Derek H. Smith Roberto Montemanni Stephanie Perkins |
| author_sort | Derek H. Smith |
| collection | DOAJ |
| description | Let <inline-formula><math display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> be an undirected graph with vertex set <i>V</i> and edge set <i>E</i>. A clique <i>C</i> of <i>G</i> is a subset of the vertices of <i>V</i> with every pair of vertices of <i>C</i> adjacent. A maximum clique is a clique with the maximum number of vertices. A tabu search algorithm for the maximum clique problem that uses an exact algorithm on subproblems is presented. The exact algorithm uses a graph coloring upper bound for pruning, and the best such algorithm to use in this context is considered. The final tabu search algorithm successfully finds the optimal or best known solution for all standard benchmarks considered. It is compared with a state-of-the-art algorithm that does not use exact search. It is slower to find the known optimal solution for most instances but is faster for five instances and finds a larger clique for two instances. |
| first_indexed | 2024-03-10T15:51:12Z |
| format | Article |
| id | doaj.art-d585068f89c24142a0406f6393b7b5d9 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T15:51:12Z |
| publishDate | 2020-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-d585068f89c24142a0406f6393b7b5d92023-11-20T16:04:39ZengMDPI AGAlgorithms1999-48932020-10-01131025310.3390/a13100253The Use of an Exact Algorithm within a Tabu Search Maximum Clique AlgorithmDerek H. Smith0Roberto Montemanni1Stephanie Perkins2School of Computing and Mathematics, University of South Wales, Pontypridd, Cardiff CF37 1DL, UKDepartment of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Via Amendola 2 (Pad. Morselli), 42122 Modena MO, ItalySchool of Computing and Mathematics, University of South Wales, Pontypridd, Cardiff CF37 1DL, UKLet <inline-formula><math display="inline"><semantics><mrow><mi>G</mi><mo>=</mo><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula> be an undirected graph with vertex set <i>V</i> and edge set <i>E</i>. A clique <i>C</i> of <i>G</i> is a subset of the vertices of <i>V</i> with every pair of vertices of <i>C</i> adjacent. A maximum clique is a clique with the maximum number of vertices. A tabu search algorithm for the maximum clique problem that uses an exact algorithm on subproblems is presented. The exact algorithm uses a graph coloring upper bound for pruning, and the best such algorithm to use in this context is considered. The final tabu search algorithm successfully finds the optimal or best known solution for all standard benchmarks considered. It is compared with a state-of-the-art algorithm that does not use exact search. It is slower to find the known optimal solution for most instances but is faster for five instances and finds a larger clique for two instances.https://www.mdpi.com/1999-4893/13/10/253combinatorial optimizationmaximum cliquehybrid algorithmtabu searchbenchmarks |
| spellingShingle | Derek H. Smith Roberto Montemanni Stephanie Perkins The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm Algorithms combinatorial optimization maximum clique hybrid algorithm tabu search benchmarks |
| title | The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm |
| title_full | The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm |
| title_fullStr | The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm |
| title_full_unstemmed | The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm |
| title_short | The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm |
| title_sort | use of an exact algorithm within a tabu search maximum clique algorithm |
| topic | combinatorial optimization maximum clique hybrid algorithm tabu search benchmarks |
| url | https://www.mdpi.com/1999-4893/13/10/253 |
| work_keys_str_mv | AT derekhsmith theuseofanexactalgorithmwithinatabusearchmaximumcliquealgorithm AT robertomontemanni theuseofanexactalgorithmwithinatabusearchmaximumcliquealgorithm AT stephanieperkins theuseofanexactalgorithmwithinatabusearchmaximumcliquealgorithm AT derekhsmith useofanexactalgorithmwithinatabusearchmaximumcliquealgorithm AT robertomontemanni useofanexactalgorithmwithinatabusearchmaximumcliquealgorithm AT stephanieperkins useofanexactalgorithmwithinatabusearchmaximumcliquealgorithm |