Idioma:

Problemas computacionais em teoria topológica dos grafos

Pocai, Rafael Veiga

Acesso online. A biblioteca também possui exemplares impressos.

Título:
Problemas computacionais em teoria topológica dos grafos
Autor: Pocai, Rafael Veiga
Orientador: Ferreira, Carlos Eduardo
Assuntos: Algoritmos De Aproximação; Número De Cruzamentos; Maxcut; Grafos De Comparabilidade; Número De Páginas; Crossing Number; Comparability Graphs; Book Thickness; Approximation Algorithms
Notas: Dissertação (Mestrado)
Descrição: 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.
DOI: 10.11606/D.45.2016.tde-27012016-090223
Editor: Biblioteca Digital de Teses e Dissertações da USP; Universidade de São Paulo; Instituto de Matemática e Estatística
Data de criação/publicação: 2015-12-11
Formato: Adobe PDF
Idioma: Português

Links

Voltar para lista de resultados