[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. / [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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:62907 |
| Date | 19 June 2023 |
| Creators | FELIPE DE OLIVEIRA |
| Contributors | SIMON RICHARD GRIFFITHS |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0024 seconds