A carregar...
Publicação
Two-phase heuristics for the k-club problem
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 606.09 KB | Adobe PDF |
Orientador(es)
Resumo(s)
Given an undirected graph G and an integer k, a k-club is a subset of nodes that induces a subgraph with diameter at most k. The k-club problem consists of identifying a maximum cardinality k-club in G. It is an NP-hard problem. The problem of checking if a given k-club is maximal or if it is a subset of a larger k-club is also NP-hard, due to the non-hereditary nature of the k-club structure. This non-hereditary nature is adverse for heuristic strategies that rely on single-element add and delete operations. In this work we propose two-phase algorithms which combine simple construction schemes with exact optimization of restricted integer models to generate near optimal solutions for the k-club problem. Numerical experiments on sets of uniform random graphs with edge densities known to be very challenging and test instances available in the literature indicate that the new algorithms are quite effective, both in terms of solution quality and running times.
Descrição
Palavras-chave
Heuristics Maximum K-Club Clique Relaxations Social Network Analysis Computational Biology
Contexto Educativo
Citação
Almeida, Maria Teresa and Filipa D. Carvalho .(2014). “Two-phase heuristics for the k-club problem”. Computers & Operations Research, Volume 52, Part A: pp 94-104. (Search PDF in 2023).
Editora
Elsevier