Planejamentos combinatórios construindo sistemas triplos de steiner

Página do item simplificado
dc.contributor.advisor1Barbosa, Rommel Melgaço
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/6228227125338610por
dc.creatorBarbosa, Enio Perez Rodrigues
dc.creator.Latteshttp://lattes.cnpq.br/8428415430012543por
dc.date.accessioned2014-09-16T14:10:30Z
dc.date.issued2011-08-26
dc.description.abstractIntuitively, the basic idea of Design Theory consists of a way to select subsets, also called blocks, of a finite set, so that some properties are satisfied. The more general case are the blocks designs. A PBD is an ordered pair (S;B), where S is a finite set of symbols, and B is a collection of subsets of S called blocks, such that each pair of distinct elements of S occur together in exactly one block of B. A Steiner Triple System is a particular case of a PBD, where every block has size only 3, being called triples. The main focus is in building technology systems. By resolvability is discussed as a Steiner Triple Systems is resolvable, and when it is not resolvable. This theory has several applications, eg, embeddings and even problems related to computational complexity.eng
dc.description.provenanceSubmitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-16T12:52:36Z No. of bitstreams: 2 Dissertação EnioPerez.pdf: 2190954 bytes, checksum: 8abd6c2cd31279e28971c632f6ed378b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)eng
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-09-16T14:10:30Z (GMT) No. of bitstreams: 2 Dissertação EnioPerez.pdf: 2190954 bytes, checksum: 8abd6c2cd31279e28971c632f6ed378b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)eng
dc.description.provenanceMade available in DSpace on 2014-09-16T14:10:30Z (GMT). No. of bitstreams: 2 Dissertação EnioPerez.pdf: 2190954 bytes, checksum: 8abd6c2cd31279e28971c632f6ed378b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2011-08-26eng
dc.description.resumoIntuitivamente, a idéia básica de um Planejamento Combinatório consiste em uma maneira de selecionar subconjuntos, também chamados de blocos, de um conjunto finito, de modo que algumas propriedades especificadas sejam satisfeitas. O caso mais geral são os planejamentos balanceados. Um PBD é um par ordenado (S;B), onde S é um conjunto finito de símbolos, e B é uma coleção de subconjuntos de S chamados blocos, tais que cada par de elementos distintos de S ocorrem juntos em exatamente um bloco de B. Um Sistema Triplo de Steiner é um caso particular de um PBD, em que todos os blocos tem tamanho único 3, sendo chamados de triplas. O foco principal está nas técnicas de construção dos sistemas. Por meio da resolubilidade se discute quando um Sistema Triplo de Steiner é resolvível e quando não é resolvível. Esta teoria possui várias aplicações, por exemplo: imersões e até mesmo problemas relacionados à complexidade computacional.por
dc.formatapplication/pdf*
dc.identifier.citationBARBOSA, Enio Perez Rodrigues. Planejamentos combinatórios construindo sistemas triplos de steiner. 2011. 90 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2011.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/3074
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.relation.references[1] BILLINGTON, E.; LINDNER, C. Embedding 5-cycle systems into pentagon triple systems. Discrete Mathematics, 309(14):4828–4834, 2009. [2] BONDY, J.; MURTY, U. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008. [3] BRYANT, D.; HORSLEY, D. A proof of lindner’s conjecture on embeddings of partial steiner triple systems. Journal of Combinatorial Designs, 17(1):63–89, 2009. [4] CAMTEPE, S.; YENER, B. Combinatorial design of key distribution mechanisms for wireless sensor networks. Computer Security–ESORICS 2004, p. 293–308, 2004. [5] CHING LI, B.; VAN REES, G. Existence of non-resolvable steiner triple systems. Journal of Combinatorial Designs, 13(1):16–24, 2005. [6] COLBOURN, C. Embedding partial steiner triple systems is np-complete. Journal of Combinatorial Theory, Series A, 35(1):100–105, 1983. [7] COLBOURN, C.; DINITZ, J. Handbook of Combinatorial Designs, (Discrete Mathematics and Its Applications). Chapman & Hall/CRC, 2007. [8] COLBOURN, C.; DINITZ, J.; STINSON, D.; OF WATERLOO. DEPT. OF COMBINATORICS, U.; OPTIMIZATION.; OF WATERLOO. FACULTY OF MATHEMATICS, U. Applications of combinatorial designs to communications, cryptography, and networking. Citeseer, 1999. [9] COLBOURN, C.; VAN OORSCHOT, P. Applications of combinatorial designs in computer science. ACM Computing Surveys (CSUR), 21(2):223–250, 1989. [10] CORMEN, T. Introduction to algorithms. The MIT press, 2001. [11] DIESTEL, R. Graph theory, Graduate Texts in Mathematics Vol. 173. Springer- Verlag, New York, 2000. Referências Bibliográficas 89 [12] DINITZ, J.; STINSON, D. Contemporary design theory: A collection of Surveys, volume 26. Wiley-Interscience, 1992. [13] DOMINGUES, H.; IEZZI, G. Álgebra moderna. Atual Editora, 2003. [14] DOYEN RICHARD M, J. Embeddings of steiner triple systems. Discrete Mathematics, 5(3):229–239, 1973. [15] DUKES, P.; LAMKEN, E.; WILSON, R. Combinatorial design theory. 2008. [16] GAREY, M.; JOHNSON, D. Computers and Intractability: A Guide to the Theory of NP-completeness. WH Freeman & Co., 1979. [17] GONÇALVES, A. Introdução à Álgebra. Instituto de Matemática Pura e Aplicada, 2001. [18] GRANNELL, M.; GRIGGS, T.; SIRAN, J. Surface embeddings of steiner triple systems. Journal of Combinatorial Designs, 6(5):325–336, 1998. [19] LAYWINE, C.; MULLEN, G. Discrete mathematics using Latin squares, volume 49. Wiley-Interscience, 1998. [20] LI, P.; TOULOUSE, M. Some np-completeness results on partial steiner triple systems and parallel classes. Ars Combinatoria, 80:45–52, 2006. [21] LINDNER, C.; QUATTROCCHI, G.; RODGER, C. Embedding steiner triple systems in hexagon triple systems. Discrete Mathematics, 309(2):487–490, 2009. [22] LINDNER, C.; RODGER, C. Design theory. Chapman & Hall/CRC, 2009. [23] MESZKA, M.; ROSA, A.; ZIOLO, I. Steiner almost self-complementary graphs and halving near-steiner triple systems. Discrete Mathematics, 309(18):5650–5654, 2009. [24] RAY-CHAUDHURI, D.; WILSON, R. Solution of kirkman’s schoolgirl problem. In: Proc. Symp. Pure Math, volume 19, p. 187–203, 1971. [25] ROSEN, K. Discrete mathematics and its applications. McGraw-Hill, 2003. [26] SCHEINERMAN, E. Matemática Discreta: Uma Introdução. Pioneira Thomson Learning, 2003. [27] SILVA, V. V. D. Números: Construção e Propriedades. Editora UFG, 2003. [28] SIPSER, M.; DE QUEIROZ, R. Introdução à teoria da computação. Thomson Learning, 2007. Referências Bibliográficas 90 [29] WALLIS, W. Introduction to Combinatorial Designs, (Discrete Mathematics and Applications). Chapman & Hall/CRC, 2007. [30] WEST, D.; OTHERS. Introduction to graph theory, volume 1. Prentice Hall Upper Saddle River, NJ, 2001por
dc.rightsAcesso Abertopor
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectPlanejamentos combinatóriospor
dc.subjectBlocospor
dc.subjectSistemas triplos de steinerpor
dc.subjectGrafospor
dc.subjectResolubilidadepor
dc.subjectImersõespor
dc.subjectDesign theoryeng
dc.subjectCombinatorial designseng
dc.subjectBlockseng
dc.subjectSteiner triple systemseng
dc.subjectGraphseng
dc.subjectResolvabilityeng
dc.subjectEmbeddingseng
dc.subjectNP-completenesseng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpor
dc.thumbnail.urlhttp://repositorio.bc.ufg.br/tede/retrieve/7689/Disserta%c3%a7%c3%a3o%20EnioPerez.pdf.jpg*
dc.titlePlanejamentos combinatórios construindo sistemas triplos de steinerpor
dc.typeDissertaçãopor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Dissertação EnioPerez.pdf
Tamanho:
2.09 MB
Formato:
Adobe Portable Document Format
Descrição:
Dissertação - PPGCCOM/RG - Enio Perez Rodrigues Barbosa
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)