Teste de propriedades em torneios (2015)
- Authors:
- Autor USP: STAGNI, HENRIQUE - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: COMBINATÓRIA PROBABILÍSTICA; TEORIA DA COMPUTAÇÃO; ALGORITMOS E ESTRUTURAS DE DADOS
- Agências de fomento:
- Language: Português
- Abstract: 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.
- Imprenta:
- Data da defesa: 26.01.2015
-
ABNT
STAGNI, Henrique. Teste de propriedades em torneios. 2015. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2015. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21072015-112930. Acesso em: 26 abr. 2024. -
APA
Stagni, H. (2015). Teste de propriedades em torneios (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21072015-112930 -
NLM
Stagni H. Teste de propriedades em torneios [Internet]. 2015 ;[citado 2024 abr. 26 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21072015-112930 -
Vancouver
Stagni H. Teste de propriedades em torneios [Internet]. 2015 ;[citado 2024 abr. 26 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21072015-112930 - Property testing and parameter estimation
- On the query complexity of estimating the distance to hereditary graph properties
- On some extremal results for order types
- Estimating parameters associated with monotone properties
- Budding yeast cell cycle modeled by context-sensitive probabilistic Boolean network
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
