• 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
 
 
Mémoire de Maîtrise
DOI
10.11606/D.45.2015.tde-21072015-112930
Document
Auteur
Nom complet
Henrique Stagni
Adresse Mail
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2015
Directeur
Jury
Kohayakawa, Yoshiharu (Président)
Hoppen, Carlos
Martin, Daniel Morgato
Titre en portugais
Teste de propriedades em torneios
Mots-clés en portugais
Lema de regularidade
Teste de propriedades
Torneios
Resumé en portugais
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.
Titre en anglais
Property testing in tournaments
Mots-clés en anglais
Property testing
Regularity lemma
Tournaments
Resumé en anglais
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.
 
AVERTISSEMENT - Regarde ce document est soumise à votre acceptation des conditions d'utilisation suivantes:
Ce document est uniquement à des fins privées pour la recherche et l'enseignement. Reproduction à des fins commerciales est interdite. Cette droits couvrent l'ensemble des données sur ce document ainsi que son contenu. Toute utilisation ou de copie de ce document, en totalité ou en partie, doit inclure le nom de l'auteur.
dtwo.pdf (866.56 Kbytes)
Date de Publication
2015-07-28
 
AVERTISSEMENT: Apprenez ce que sont des œvres dérivées cliquant ici.
Tous droits de la thèse/dissertation appartiennent aux auteurs
Centro de Informática de São Carlos
Bibliothèque Numérique de Thèses et Mémoires de l'USP. Copyright © 2001-2021. Tous droits réservés.