Use este identificador para citar ou linkar para este item:
http://repositorio.ufc.br/handle/riufc/16943| Tipo: | Dissertação |
| Título: | Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos |
| Título em inglês: | Decomposition and width in tree of graphs to glide free of cycles induced pairs |
| Autor(es): | Silva, Aline Alves da |
| Orientador: | Sales, Cláudia Linhares |
| Coorientador: | Corrêa, Ricardo Cordeiro |
| Palavras-chave: | Ciência da computação;Grafos planares, grafos livres de buracos pares, largura em árvore, teoria de Grafos |
| Data do documento: | 2007 |
| Citação: | SILVA, Aline Alves da. Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos. 2007. 81 f. Dissertação (mestrado) - Universidade Federal do Ceará, Departamento de Computação, Fortaleza-CE, 2007. |
| Resumo: | 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. |
| Abstract: | 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. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/16943 |
| Aparece nas coleções: | DCOMP - Teses defendidas na UFC |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 2007_dis_aasilva.pdf | 620,37 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.