• 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
 
 
Dissertação de Mestrado
DOI
10.11606/D.45.2015.tde-21072015-112930
Documento
Autor
Nome completo
Henrique Stagni
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2015
Orientador
Banca examinadora
Kohayakawa, Yoshiharu (Presidente)
Hoppen, Carlos
Martin, Daniel Morgato
Título em português
Teste de propriedades em torneios
Palavras-chave em português
Lema de regularidade
Teste de propriedades
Torneios
Resumo em 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 em inglês
Property testing in tournaments
Palavras-chave em inglês
Property testing
Regularity lemma
Tournaments
Resumo em 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.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
dtwo.pdf (866.56 Kbytes)
Data de Publicação
2015-07-28
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2018. Todos os direitos reservados.