Solução Exata do Problema da Clique Máxima
Resumo
Vários algoritmos para o Problema da Clique Máxima são encontrados na literatura, grande parte deles empregando a técnica de Branch & Bound. Neste trabalho é descrito um algoritmo genérico de Branch & Bound para solução exata do Problema da Clique Máxima, são revisados oito algoritmos disponíveis na literatura e cada um dos algoritmos é descrito como uma modificação do algoritmo genérico. Implementamos estes algoritmos e executamos experimentos cujos resultados são apresentados para comparação.
Referências
Bellare, M., Goldreich, O., e Sudan, M. (1995). Free bits, pcps and non-approximability-towards tight results. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, p. 422–431. IEEE.
Bron, C. e Kerbosch, J. (1973). Algorithm 457: finding all cliques of an undirected graph. Commun. ACM, 16(9):575–577.
Carmo, R. e Züge, A. (2011). Branch and bound algorithms for the maximum clique problem under a unified framework. Journal of the Brazilian Computer Society, p. 1–15.
Carraghan, R. e Pardalos, P. M. (1990). An exact algorithm for the maximum clique problem. Operations Research Letters, 9(6).
Downey, R. e Fellows, M. (1999). Parameterized complexity, volume 5. Springer New York.
Duarte Jr., E. P., Garrett, T., Bona, L. C. E., Carmo, R., e Zuge, A. P. (2010). Finding stable cliques of planetlab nodes. In 2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN), p. 317–322. IEEE.
Fahle, T. (2002). Simple and fast: Improving a branch-and-bound algorithm for maximum clique. In Lecture Notes in Computer Science, p. 47–86. Springer Berlin / Heidelberg.
Garey, M. e Johnson, D. (1979). Computers and intractability. Freeman San Francisco.
Jian, T. (1986). An o(20.304n) algorithm for solving maximum independent set problem. IEEE Trans. Comput., 35(9):847–851.
Konc, J. e Janezic, D. (2007). An improved branch and bound algorithm for the maximum clique problem. MATCH Communications in Mathematical and in Computer Chemistry.
Moon, J. e Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1):23–28.
Östergård, P. R. (2002). A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1-3):197–207.
Robson, J. (1986). Algorithms for maximum independent sets. Journal of Algorithms, 7(3):425–440.
Tarjan, R. E. e Trojanowski, A. E. (1976). Finding a maximum independent set. Technical report, Computer Science Department, School of Humanities and Sciences, Stanford University, Stanford, CA, USA.
Tomita, E. e Kameda, T. (2007). An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. Journal of Global Optimization, 37(1):95–111.
Tomita, E. e Seki, T. (2003). An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique. Springer Berlin/Heidelberg.
Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., e Wakatsuki, M. (2010). A simple and faster branch-and-bound algorithm for finding a maximum clique. In Rahman, M. e Fujita, S., editors, WALCOM: Algorithms and Computation, volume 5942, chapter 18, p. 191–203. Springer Berlin Heidelberg, Berlin, Heidelberg.
Tomita, E., Tanaka, A., e Takahashi, H. (2006). The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1):28–42.
Züge, A. (2011). Solução exata do problema da clique máxima. Master’s thesis, Universidade Federal do Paraná.
Bron, C. e Kerbosch, J. (1973). Algorithm 457: finding all cliques of an undirected graph. Commun. ACM, 16(9):575–577.
Carmo, R. e Züge, A. (2011). Branch and bound algorithms for the maximum clique problem under a unified framework. Journal of the Brazilian Computer Society, p. 1–15.
Carraghan, R. e Pardalos, P. M. (1990). An exact algorithm for the maximum clique problem. Operations Research Letters, 9(6).
Downey, R. e Fellows, M. (1999). Parameterized complexity, volume 5. Springer New York.
Duarte Jr., E. P., Garrett, T., Bona, L. C. E., Carmo, R., e Zuge, A. P. (2010). Finding stable cliques of planetlab nodes. In 2010 IEEE/IFIP International Conference on Dependable Systems & Networks (DSN), p. 317–322. IEEE.
Fahle, T. (2002). Simple and fast: Improving a branch-and-bound algorithm for maximum clique. In Lecture Notes in Computer Science, p. 47–86. Springer Berlin / Heidelberg.
Garey, M. e Johnson, D. (1979). Computers and intractability. Freeman San Francisco.
Jian, T. (1986). An o(20.304n) algorithm for solving maximum independent set problem. IEEE Trans. Comput., 35(9):847–851.
Konc, J. e Janezic, D. (2007). An improved branch and bound algorithm for the maximum clique problem. MATCH Communications in Mathematical and in Computer Chemistry.
Moon, J. e Moser, L. (1965). On cliques in graphs. Israel Journal of Mathematics, 3(1):23–28.
Östergård, P. R. (2002). A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1-3):197–207.
Robson, J. (1986). Algorithms for maximum independent sets. Journal of Algorithms, 7(3):425–440.
Tarjan, R. E. e Trojanowski, A. E. (1976). Finding a maximum independent set. Technical report, Computer Science Department, School of Humanities and Sciences, Stanford University, Stanford, CA, USA.
Tomita, E. e Kameda, T. (2007). An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. Journal of Global Optimization, 37(1):95–111.
Tomita, E. e Seki, T. (2003). An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique. Springer Berlin/Heidelberg.
Tomita, E., Sutani, Y., Higashi, T., Takahashi, S., e Wakatsuki, M. (2010). A simple and faster branch-and-bound algorithm for finding a maximum clique. In Rahman, M. e Fujita, S., editors, WALCOM: Algorithms and Computation, volume 5942, chapter 18, p. 191–203. Springer Berlin Heidelberg, Berlin, Heidelberg.
Tomita, E., Tanaka, A., e Takahashi, H. (2006). The worst-case time complexity for generating all maximal cliques and computational experiments. Theoretical Computer Science, 363(1):28–42.
Züge, A. (2011). Solução exata do problema da clique máxima. Master’s thesis, Universidade Federal do Paraná.
Publicado
16/07/2012
Como Citar
ZÜGE, Alexandre Prusch; CARMO, Renato.
Solução Exata do Problema da Clique Máxima. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 15. , 2012, Curitiba/PR.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2012
.
p. 79-84.
ISSN 2763-8820.
