Submitted 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) / Approved 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) / Made 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-10 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / In 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. / Neste 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.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/4821 |
| Date | 10 April 2015 |
| Creators | Duarte, Márcio Antônio |
| Contributors | Barbosa, Rommel Melgaço, Szwarcfiter, Jayme L., Barbosa, Rommel Melgaço, Yanasse, Horacio Hideki, Oliveira, Carla Silva, Coelho, Erika Morais Martins, Silva, Hebert Coelho da |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 3671711205811204509, -2555911436985713659 |
Page generated in 0.0032 seconds