Um algoritmo exato para biclique-coloração

  • Guilherme de C. M. Gomes
  • Vinicius Fernandes dos Santos

Resumo


O número biclique-cromático B(G) de um grafo G = (V; E) é o menor inteiro k tal que existe uma k-coloração dos vertices de G com a propriedade de que nenhuma biclique maximal de G seja monocromática. Trabalhos recentes provaram que o problema de se computar B(G) para um grafo G é 2p-completo para qualquer k 2. Nosso principal resultado neste trabalho é um algoritmo baseado em inclusão-exclusão de complexidade O (2n) para se computar B(G) de forma exata.

Publicado
06/07/2017
Como Citar

Selecione um Formato
GOMES, Guilherme de C. M.; DOS SANTOS, Vinicius Fernandes. Um algoritmo exato para biclique-coloração. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2017 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2017.3183.