The maximum k-colorable subgraph problem (2024)
- Authors:
- Autor USP: OLIVEIRA, THIAGO LIMA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2024.tde-25082025-111037
- Subjects: FUNÇÃO TETA; PROGRAMAÇÃO MATEMÁTICA; OTIMIZAÇÃO COMBINATÓRIA
- Keywords: Conjuntos estáveis; Função theta de Lovász; Lovászs theta function; Programação semidefinida; Semidefinite programming; Stable sets
- Agências de fomento:
- Language: Inglês
- Abstract: O tema principal desta dissertação de mestrado é o estudo do problema do subgrafo máximo k-colorível usando técnicas de teoria poliédrica, relaxações convexas e programação semidefinida. Dado um grafo, deseja-se encontrar o maior subgrafo induzido cujos vértices possam ser coloridos com k cores. No caso k = 1, o problema se torna o clássico problema do conjunto estável máximo. Narasimhan introduziu uma cota superior para este problema, que pode ser computada em tempo polinomial, e que generaliza a função theta de Lovász. Nesta dissertação, revisamos os resultados básicos sobre o problema do conjunto estável máximo e sua relaxação semidefinida, exibimos a cota introduzida por Narasimhan, e desenvolvemos novas conexões baseadas no trabalho de Lovász
- Imprenta:
- Data da defesa: 12.07.2024
- 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
OLIVEIRA, Thiago Lima. The maximum k-colorable subgraph problem. 2024. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2024. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-25082025-111037/. Acesso em: 01 abr. 2026. -
APA
Oliveira, T. L. (2024). The maximum k-colorable subgraph problem (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-25082025-111037/ -
NLM
Oliveira TL. The maximum k-colorable subgraph problem [Internet]. 2024 ;[citado 2026 abr. 01 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-25082025-111037/ -
Vancouver
Oliveira TL. The maximum k-colorable subgraph problem [Internet]. 2024 ;[citado 2026 abr. 01 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-25082025-111037/
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
