XINFORMAÇÕES SOBRE DIREITOS AUTORAIS
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.
A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.
A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.
A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital
Título: UMA CARACTERIZAÇÃO DE PROPRIEDADES TESTÁVEIS NO MODELO DE GRAFOS DENSOS Autor: FELIPE DE OLIVEIRA
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Colaborador(es):
SIMON RICHARD GRIFFITHS - ORIENTADOR
Nº do Conteudo: 62907
Catalogação: 19/06/2023 Idioma(s): INGLÊS - ESTADOS UNIDOS
Tipo: TEXTO Subtipo: TESE
Natureza: PUBLICAÇÃO ACADÊMICA
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
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
Resumo:
Título: UMA CARACTERIZAÇÃO DE PROPRIEDADES TESTÁVEIS NO MODELO DE GRAFOS DENSOS Autor: FELIPE DE OLIVEIRA
Nº do Conteudo: 62907
Catalogação: 19/06/2023 Idioma(s): INGLÊS - ESTADOS UNIDOS
Tipo: TEXTO Subtipo: TESE
Natureza: PUBLICAÇÃO ACADÊMICA
Nota: Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio.
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
Resumo:
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.
| Descrição | Arquivo |
| NA ÍNTEGRA |
