O número envoltório P3 e o número envoltório geodético em produtos de grafos

Página do item simplificado
dc.contributor.advisor-co1Szwarcfiter, Jayme Luiz
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/2002515486942024por
dc.contributor.advisor1Coelho, Erika Morais Martins
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/9389487015938509por
dc.contributor.referee1Coelho, Erika Morais Martins
dc.contributor.referee1Latteshttp://lattes.cnpq.br/9389487015938509por
dc.contributor.referee2Szwarcfiter, Jayme Luiz
dc.contributor.referee2Latteshttp://lattes.cnpq.br/2002515486942024por
dc.contributor.referee3Centeno, Carmen Cecilia
dc.contributor.referee4Dias, Elisângela Silva
dc.creatorNascimento, Julliano Rosa
dc.creator.Latteshttp://lattes.cnpq.br/8971175373328824por
dc.date.accessioned2016-12-13T19:11:50Z
dc.date.issued2016-11-30
dc.description.abstractIn this work, we consider the parameter hull number in two graph convexities, the P3- convexity and the geodetic convexity. In the P3-convexity, we present results on the P3- hull number on the Cartesian product, strong product and lexicographic product of graphs. In special, regarding to the Cartesian product, we proved a complexity result, in which we show, given a graph G resulting of a Cartesian product of two graphs and a positive integer k, is NP-complete to decide whether the P3-hull number of G is less than or equal k. We also consider the P3-hull number on complementary prisms GG of connected graphs G and G, in which we show a tighter upper bound than that found in the literature. In the geodetic convexity, we show results of the hull number on complementary prisms GG when G is a tree, when G is a disconnected graph and when G is a cograph. Finally, we also show that in the geodetic convexity, the hull number on the complementary prism GG is unlimited on connected graphs G and G, unlike what happens in the P3-convexityeng
dc.description.provenanceSubmitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2016-12-09T16:43:52Z No. of bitstreams: 2 Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceApproved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-12-13T19:11:50Z (GMT) No. of bitstreams: 2 Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceMade available in DSpace on 2016-12-13T19:11:50Z (GMT). No. of bitstreams: 2 Dissertação - Julliano Rosa Nascimento - 2016.pdf: 1812313 bytes, checksum: 9bdaa6ddbbe1dd9ce1e9ccdea8016eaf (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-11-30eng
dc.description.resumoNesta dissertação, consideramos o parâmetro número envoltório em duas convexidades em grafos, a convexidade P3 e a convexidade geodética. Na convexidade P3, obtivemos resultados do número envoltório P3 para o produto Cartesiano, produto forte e produto lexicográfico de grafos. Em especial, em relação ao produto Cartesiano, obtivemos um resultado de complexidade, no qual mostramos que, dado um grafo G, resultante de um produto Cartesiano de dois grafos e um inteiro positivo k, é NP-completo decidir se o número envoltório P3 de G é menor ou igual a k. Também consideramos o número envoltório P3 para prismas complementares GG de grafos G e G conexos, em que mostramos um limite superior um pouco mais justo do que o encontrado na literatura. Na convexidade geodética, mostramos resultados do número envoltório para prismas complementares GG quando G é uma árvore, quando G é um grafo desconexo e quando G é um cografo. Por fim, também mostramos que na convexidade geodética o número envoltório do prisma complementar GG pode ser ilimitado para grafos G e G ambos conexos, diferentemente do que ocorre na convexidade P3.por
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESpor
dc.formatapplication/pdf*
dc.identifier.citationNASCIMENTO, J. R. O número envoltório P3 e o número envoltório geodético em produtos de grafos. 2016. 87 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2016.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/6583
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.subjectConvexidade P3por
dc.subjectConvexidade geodéticapor
dc.subjectNúmero envoltóriopor
dc.subjectProdutos de grafospor
dc.subjectPrismas complementarespor
dc.subjectP3-convexityeng
dc.subjectGeodetic convexityeng
dc.subjectHull numbereng
dc.subjectGraph productseng
dc.subjectComplementary prismseng
dc.subject.cnpqCIENCIA DA COMPUTACAO::MATEMATICA DA COMPUTACAOpor
dc.titleO número envoltório P3 e o número envoltório geodético em produtos de grafospor
dc.title.alternativeThe P3-hull number and the geodetic hull number in graph productseng
dc.typeDissertaçãopor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Dissertação - Julliano Rosa Nascimento - 2016.pdf
Tamanho:
1.73 MB
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

Mestrado em Ciência da Computação (INF)