Detalhes bibliográficos
| Ano de defesa: |
2015 |
| Autor(a) principal: |
Pocai, Rafael Veiga |
| Orientador(a): |
Não Informado pela instituição |
| Banca de defesa: |
Não Informado pela instituição |
| Tipo de documento: |
Dissertação
|
| Tipo de acesso: |
Acesso aberto |
| Idioma: |
por |
| Instituição de defesa: |
Biblioteca Digitais de Teses e Dissertações da USP
|
| Programa de Pós-Graduação: |
Não Informado pela instituição
|
| Departamento: |
Não Informado pela instituição
|
| País: |
Não Informado pela instituição
|
| Palavras-chave em Português: |
|
| Link de acesso: |
http://www.teses.usp.br/teses/disponiveis/45/45134/tde-27012016-090223/
|
Resumo: |
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. |
