Empacotamento de bicliques em grafos bipartidos (2012)
- Authors:
- Autor USP: FREIRE, ALEXANDRE DA SILVA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/T.45.2012.tde-26112012-161435
- Assunto: COMBINATÓRIA
- Agências de fomento:
- Language: Português
- Abstract: Nesta tese, estudamos o problema de empacotamento de bicliques. Um biclique é um grafo bipartido completo. No problema de empacotamento de bicliques são dados um inteiro k e um grafo bipartido G e deseja-se encontrar um conjunto de k bicliques, subgrafos de G, dois a dois disjuntos nos vértices, tal que a quantidade total de arestas dos bicliques escolhidos seja máxima. No caso em que k = 1, temos o problema de biclique máximo. Esses dois problemas possuem aplicações na área de Bioinformática. Mantemos neste trabalho um enfoque prático, no sentido de que nosso interesse é resolver instâncias desses dois problemas com tamanho razoavelmente grande. Para isso, utilizamos técnicas de Programação Linear Inteira. Para avaliar os métodos propostos aqui, mostramos resultados de experimentos computacionais feitos com instâncias vindas de aplicações e também com instâncias geradas aleatoriamente.
- Imprenta:
- Data da defesa: 02.10.2012
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
FREIRE, Alexandre da Silva. Empacotamento de bicliques em grafos bipartidos. 2012. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2012. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-26112012-161435. Acesso em: 06 maio 2026. -
APA
Freire, A. da S. (2012). Empacotamento de bicliques em grafos bipartidos (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-26112012-161435 -
NLM
Freire A da S. Empacotamento de bicliques em grafos bipartidos [Internet]. 2012 ;[citado 2026 maio 06 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-26112012-161435 -
Vancouver
Freire A da S. Empacotamento de bicliques em grafos bipartidos [Internet]. 2012 ;[citado 2026 maio 06 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-26112012-161435
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
