Tabu search with graph reduction for finding maximum balanced bicliques in bipartite graphs. (January 2019)

• Record Type: Journal Article
• Authors: Zhou, Yi; Hao, Jin-Kao
• Is Part Of: Engineering applications of artificial intelligence. Volume 77(2019)
• Page Start: 86
• Page End: 97
• Publication Date: 2019-01
• Subjects: Heuristics -- Clique problems -- Graph reduction -- Tabu search -- Complex networks; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2018.09.017
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: 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 novel metaheuristic algorithm, which combines an effective constraint-based tabu search procedure 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.