Tabu search with graph reduction for finding maximum balanced bicliques in bipartite graphs
| Autor: | Jin-Kao Hao, Yi Zhou |
|---|---|
| Přispěvatelé: | University of Electronic Science and Technology of China (UESTC), Laboratoire d'Etudes et de Recherche en Informatique d'Angers (LERIA), Université d'Angers (UA), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
0209 industrial biotechnology
Theoretical computer science Computer science Clique problems 02 engineering and technology complex networks Graph reduction [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] Complete bipartite graph Graph Tabu search Constraint (information theory) 020901 industrial engineering & automation Artificial Intelligence Control and Systems Engineering 0202 electrical engineering electronic engineering information engineering Benchmark (computing) Bipartite graph tabu search Heuristics 020201 artificial intelligence & image processing Electrical and Electronic Engineering Metaheuristic |
| Zdroj: | Engineering Applications of Artificial Intelligence Engineering Applications of Artificial Intelligence, Elsevier, 2019, 77, pp.86-97. ⟨10.1016/j.engappai.2018.09.017⟩ |
| ISSN: | 0952-1976 |
| DOI: | 10.1016/j.engappai.2018.09.017⟩ |
| Popis: | International audience; The Maximum Balanced Biclique Problem is a relevant graph model with a number of applications in diverse domains. However, the problem is NP-hard and thus computationally challenging. In this paper, we introduce a novelmetaheuristic algorithm, which combines an effective constraint-basedtabu searchprocedure and two dedicated graph reduction techniques. We verify the effectiveness of the algorithm on 30 classical random benchmark graphs and 25 very large real-life sparse graphs from the popular Koblenz Network Collection (KONECT). The results show that the algorithm improves the best-known results (new lower bounds) for 10 classical benchmarks and obtains the optimal solutions for 14 KONECT instances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect