Título
[en] A CHARACTERIZATION OF TESTABLE GRAPH PROPERTIES IN THE DENSE GRAPH MODEL
Título
[pt] UMA CARACTERIZAÇÃO DE PROPRIEDADES TESTÁVEIS NO MODELO DE GRAFOS DENSOS
Autor
[pt] FELIPE DE OLIVEIRA
Vocabulário
[pt] ALGORITMOS ALEATORIZADOS
Vocabulário
[pt] O LEMA DE REGULARIDADE DE SZEMEREDI
Vocabulário
[pt] TESTAGEM DE PROPRIEDADES
Vocabulário
[pt] ALGORITMOS EM GRAFOS
Vocabulário
[pt] ALGORITMOS DE APROXIMACAO
Vocabulário
[en] RANDOMIZED ALGORITHMS
Vocabulário
[en] SZEMEREDI S REGULARITY LEMMA
Vocabulário
[en] PROPERTY TESTING
Vocabulário
[en] GRAPH ALGORITHMS
Vocabulário
[en] APPROXIMATION ALGORITHMS
Resumo
[pt] Consideramos, nesta dissertação, a questão de determinar se um grafo
tem uma propriedade P, tal como G é livre de triângulos ou G é 4-
colorível. Em particular, consideramos para quais propriedades P existe um
algoritmo aleatório com probabilidades de erro constantes que aceita grafos que
satisfazem P e rejeita grafos que são epsilon-longe de qualquer grafo que o satisfaça.
Se, além disso, o algoritmo tiver complexidade independente do tamanho
do grafo, a propriedade é dita testável. Discutiremos os resultados de Alon,
Fischer, Newman e Shapira que obtiveram uma caracterização combinatória de
propriedades testáveis de grafos, resolvendo um problema em aberto levantado
em 1996. Essa caracterização diz informalmente que uma propriedade P de
um grafo é testável se e somente se testar P pode ser reduzido a testar a
propriedade de satisfazer uma das finitas partições Szemerédi.
Resumo
[en] We consider, in this thesis, the question of determining if a graph has a
property P such as G is triangle-free or G is 4-colorable. In particular,
we consider for which properties P there exists a random algorithm with
constant error probabilities that accept graphs that satisfy P and reject graphs
that are epsilon-far from any graph that satisfies it. If, in addition, the algorithm
has complexity independent of the size of the graph, the property is called
testable. We will discuss the results of Alon, Fischer, Newman, and Shapira
that obtained a combinatorial characterization of testable graph properties,
solving an open problem raised in 1996. This characterization informally says
that a graph property P is testable if and only if testing P can be reduced to
testing the property of satisfying one of finitely many Szemerédi-partitions.
Orientador(es)
SIMON RICHARD GRIFFITHS
Banca
SIMON RICHARD GRIFFITHS
Banca
TAISA LOPES MARTINS
Banca
GUILHERME OLIVEIRA MOTA
Banca
RANGEL BALDASSO
Catalogação
2023-06-19
Apresentação
2023-04-28
Tipo
[pt] TEXTO
Formato
application/pdf
Idioma(s)
INGLÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=62907@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=62907@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.62907
Arquivos do conteúdo
NA ÍNTEGRA PDF