Problemas computacionais em teoria topológica dos grafos (2015)
- Authors:
- Autor USP: POCAI, RAFAEL VEIGA - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2016.tde-27012016-090223
- Assunto: TEORIA DOS GRAFOS
- Agências de fomento:
- Language: Português
- Abstract: Este trabalho tem por objetivo estudar os problemas computacionais que surgem ao se relacionar grafos com superfícies bidimensionais, dando especial atenção aos problemas do número de cruzamentos mínimo no plano (CROSSING NUMBER) e a problemas relacionados ao desenho de grafos em livros. Apresentamos uma redução do problema MULTICUT para CROSSING NUMBER, além de um resultado de complexidade em grafos de comparabilidade baseado em um resultado conhecido para desenhos em livros.
- Imprenta:
- Data da defesa: 11.12.2015
- 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
POCAI, Rafael Veiga. Problemas computacionais em teoria topológica dos grafos. 2015. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2015. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-27012016-090223. Acesso em: 18 mar. 2026. -
APA
Pocai, R. V. (2015). Problemas computacionais em teoria topológica dos grafos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-27012016-090223 -
NLM
Pocai RV. Problemas computacionais em teoria topológica dos grafos [Internet]. 2015 ;[citado 2026 mar. 18 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-27012016-090223 -
Vancouver
Pocai RV. Problemas computacionais em teoria topológica dos grafos [Internet]. 2015 ;[citado 2026 mar. 18 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-27012016-090223
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
