SILVA, Aline Alves da. Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos. 2007. 71 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Departamento de Computação, Fortaleza-CE, 2007. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T19:42:38Z
No. of bitstreams: 1
2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-20T19:43:21Z (GMT) No. of bitstreams: 1
2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Made available in DSpace on 2016-05-20T19:43:21Z (GMT). No. of bitstreams: 1
2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5)
Previous issue date: 2007 / The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10£10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the ¯rst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order. / Os conceitos de Decomposição em Árvore e Largura em Árvore foram introduzidos por Robertson e Seymour em sua série de artigos sobre menores de grafos, publicados ao longo da década de 90. Sabe-se que muitos problemas NP - difíceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposição em Árvore de G de largura limitada. Logo, limitar a largura em árvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras métricas limitadas em valores baixos (por exemplo, número cromático), não possui largura em árvore limitada. Desta forma, uma alternativa é restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nós investigamos a classe dos grafos planares livres de buracos pares. Nós mostramos que se G é um grafo planar livre de buracos pares, então ele não contém uma subdivisão de uma grade 10 £ 10. Portanto, se os menores grades de G são obtidos de subdivisões G tem largura em árvore no máximo 49. Além disso, dois algoritmos não exatos polinomiais para computar uma decomposição em árvore de um grafo planar livre de buracos pares são apresentados, ambos baseados em caracterizações conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposição em árvore é construída a partir de grafos básicos pela concatenação de decomposições em árvores de pedaços pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposição em árvore é construída pela inclusão dos vértices de G um a um, seguindo sua ordem bi-simplicial.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufc.br:riufc/16943 |
| Date | January 2007 |
| Creators | Silva, Aline Alves da |
| Contributors | Corrêa, Ricardo Cordeiro, Sales , Cláudia Linhares |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds