Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for +publisher:"Universidade Federal do Ceará" +contributor:("Sulamita Klein"). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters

1. Aline Alves da Silva. DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos.

Degree: Master, 2007, Universidade Federal do Ceará

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.

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.

Advisors/Committee Members: Ricardo Cordeiro CorrÃa, Sulamita Klein, ClÃudia Linhares Sales.

Subjects/Keywords: CIENCIA DA COMPUTACAO; Grafos planares, grafos livres de buracos pares, largura em Ãrvore, teoria de Grafos.; Planar Graphs, even-hole-free graphs, treewidth, graph theory

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Silva, A. A. d. (2007). DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos. (Masters Thesis). Universidade Federal do Ceará. Retrieved from http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324 ;

Chicago Manual of Style (16th Edition):

Silva, Aline Alves da. “DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos.” 2007. Masters Thesis, Universidade Federal do Ceará. Accessed January 19, 2021. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324 ;.

MLA Handbook (7th Edition):

Silva, Aline Alves da. “DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos.” 2007. Web. 19 Jan 2021.

Vancouver:

Silva AAd. DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos. [Internet] [Masters thesis]. Universidade Federal do Ceará 2007. [cited 2021 Jan 19]. Available from: http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324 ;.

Council of Science Editors:

Silva AAd. DecomposiÃÃo e largura em Ãrvore de grafos planares livres de ciclos pares induzidos. [Masters Thesis]. Universidade Federal do Ceará 2007. Available from: http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=1324 ;

.