Sobre convexidade em prismas complementares

Página do item simplificado
dc.contributor.advisor-co1Szwarcfiter, Jayme L.
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/2002515486942024por
dc.contributor.advisor1Barbosa, Rommel Melgaço
dc.contributor.advisor1Lattes http://lattes.cnpq.br/6228227125338610por
dc.contributor.referee1Barbosa, Rommel Melgaço
dc.contributor.referee2Yanasse, Horacio Hideki
dc.contributor.referee3Oliveira, Carla Silva
dc.contributor.referee4Coelho, Erika Morais Martins
dc.contributor.referee5Silva, Hebert Coelho da
dc.creatorDuarte, Márcio Antônio
dc.creator.Latteshttp://lattes.cnpq.br/9907691146700229por
dc.date.accessioned2015-10-29T10:04:41Z
dc.date.issued2015-04-10
dc.description.abstractIn this work, we present some related results, especially the properties algoritimics and of complexity of a product of graphs called complementary prism. Answering some questions left open by Haynes, Slater and van der Merwe, we show that the problem of click, independent set and k-dominant set is NP-Complete for complementary prisms in general. Furthermore, we show NP-completeness results regarding the calculation of some parameters of the P3-convexity for the complementary prism graphs in general, as the P3-geodetic number, P3-hull number and P3-Carathéodory number. We show that the calculation of P3-geodetic number is NP-complete for complementary prism graphs in general. As for the P3-hull number, we can show that the same can be efficiently computed in polynomial time. For the P3-Carathéodory number, we show that it is NPcomplete complementary to prisms bipartite graphs, but for trees, this may be calculated in polynomial time and, for class of cografos, calculating the P3-Carathéodory number of complementary prism of these is 3. We also found a relationship between the cardinality Carathéodory set of a graph and a any Carathéodory set of complementary prism. Finally, we established an upper limit calculation the parameters: geodetic number, hull number and Carathéodory number to operations complementary prism of path, cycles and complete graphs considering the convexities P3 and geodesic.eng
dc.description.provenanceSubmitted by Cássia Santos (cassia.bcufg@gmail.com) on 2015-10-27T14:37:06Z No. of bitstreams: 2 Tese - Marcio Antonio Duarte - 2015.pdf: 457015 bytes, checksum: 1f57686628e44a0cebc1fee7aaf0bcfc (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)eng
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-29T10:04:41Z (GMT) No. of bitstreams: 2 Tese - Marcio Antonio Duarte - 2015.pdf: 457015 bytes, checksum: 1f57686628e44a0cebc1fee7aaf0bcfc (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)eng
dc.description.provenanceMade available in DSpace on 2015-10-29T10:04:41Z (GMT). No. of bitstreams: 2 Tese - Marcio Antonio Duarte - 2015.pdf: 457015 bytes, checksum: 1f57686628e44a0cebc1fee7aaf0bcfc (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-04-10eng
dc.description.resumoNeste trabalho, apresentamos alguns resultados relacionados, principalmente às propriedades algorítmicas e de complexidade de um produto de grafos chamado prisma complementar. Respondendo algumas questões deixadas em aberto por Haynes, Slater e van der Merwe, mostramos o problema de clique, conjunto independente e conjunto com kdominantes é NP-Completo para prismas complementares em geral. Além disso, mostramos resultados de NP-completude em relação ao cálculo de alguns parâmetros da convexidade P3 para o prisma complementar de grafos em geral, como o número P3, número envoltório P3 e número de Carathéodory. Mostramos que o cálculo do número P3 é NPcompleto para o prisma complementar de grafos em geral. Já para o número envoltório P3, mostramos que o mesmo pode ser calculado de forma eficiente em tempo polinomial. Para o número de Carathéodory, mostramos que é NP-completo para os prismas complementares de grafos bipartidos, mas que para árvores, este pode ser calculado em tempo polinomial e ainda, para classe dos cografos, o cálculo do número de Carathéodory do prisma complementar desses é 3. Encontramos também, uma relação entre a cardinalidade de um conjunto de Carathéodory de um grafo qualquer e um conjunto de Carathéodory do seu prisma complementar. Por fim, estabelecemos um limite superior do cálculo dos parâmetros: número geodésico, número envoltório e número de Carathéodory para operações prisma complementar de grafos caminho, ciclos e completos considerando as convexidades P3 e geodésica.por
dc.description.sponsorshipConselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPqpor
dc.formatapplication/pdf*
dc.identifier.citationDUARTE, M. A. Sobre convexidade em prismas complementares. 2015. 68 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2015.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/4821
dc.languageporpor
dc.publisherUniversidade Federal de Goiáspor
dc.publisher.countryBrasilpor
dc.publisher.departmentInstituto de Informática - INF (RG)por
dc.publisher.initialsUFGpor
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)por
dc.rightsAcesso Abertopor
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectTeoria dos grafospor
dc.subjectConvexidadepor
dc.subjectNP-completudepor
dc.subjectPrismas complementarespor
dc.subjectGraph theoryeng
dc.subjectConvexityeng
dc.subjectNP-completeeng
dc.subjectComplementary prismseng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor
dc.thumbnail.urlhttp://repositorio.bc.ufg.br/tede/retrieve/22275/Tese%20-%20Marcio%20Antonio%20Duarte%20-%202015.pdf.jpg*
dc.titleSobre convexidade em prismas complementarespor
dc.title.alternativeResults on convexity complementary prismseng
dc.typeTesepor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Tese - Marcio Antonio Duarte - 2015.pdf
Tamanho:
446.3 KB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Doutorado em Ciência da Computação em Rede - UFMS/UFG (INF)