• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
10.11606/D.45.2015.tde-21072015-112930
Documento
Autor
Nombre completo
Henrique Stagni
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2015
Director
Tribunal
Kohayakawa, Yoshiharu (Presidente)
Hoppen, Carlos
Martin, Daniel Morgato
Título en portugués
Teste de propriedades em torneios
Palabras clave en portugués
Lema de regularidade
Teste de propriedades
Torneios
Resumen en portugués
Teste de propriedades em grafos consiste no estudo de algoritmos aleatórios sublineares que determinam se um grafo $G$ de entrada com $n$ vértices satisfaz uma dada propriedade ou se é necessário adicionar ou remover mais do que $\epsilon{n \choose 2}$ arestas para fazer $G$ satisfazê-la, para algum parâmetro $\epsilon$ de erro fixo. Uma propriedade de grafos $P$ é dita testável se, para todo $\epsilon > 0$, existe um tal algoritmo para $P$ cujo tempo de execução é independente de $n$. Um dos resultados de maior importância nesta área, provado por Alon e Shapira, afirma que toda propriedade hereditária de grafos é testável. Neste trabalho, apresentamos resultados análogos para torneios --- grafos completos nos quais são dadas orientações para cada aresta.
Título en inglés
Property testing in tournaments
Palabras clave en inglés
Property testing
Regularity lemma
Tournaments
Resumen en inglés
Graph property testing is the study of randomized sublinear algorithms which decide if an input graph $G$ with $n$ vertices satisfies a given property or if it is necessary to add or remove more than $\epsilon{n \choose 2}$ edges to make $G$ satisfy it, for some fixed error parameter $\epsilon$ . A graph property $P$ is called testable if, for every $\epsilon > 0$, there is such an algorithm for $P$ whose run time is independent of $n$. One of the most important results in this area is due to Alon and Shapira, who showed that every hereditary graph property is testable. In this work, we show analogous results for tournaments --- complete graphs in which every edge is given an orientation.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
dtwo.pdf (866.56 Kbytes)
Fecha de Publicación
2015-07-28
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.