CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / The concept of treewidth was introduced by Robertson and Seymour. Treewidth may be defined as the size of the largest vertex set in a tree decomposition.
Recent results show that several NP-Complete problems can be solved in polynomial time, or linear, when restricted to graphs with small treewidth.
In our bibliographic research, we focus attention on the calculation of lower bounds for the treewidth and we described, in our dissertation, some of the principal results already available in the literature.
We realize that linear-integer formulations for determining the treewidth are very limited in the literature and there are no studies available on the polyhedra associated with them.
The Elimination Order Formulation (EOF) has been proposed by Koster and Bodlaender. It is based on orderly disposal of vertices and the relationship between the treewidth of a graph and its chordalizations.
As a result of our study, we present a simplification of EOF formulation, we show that the polyhedron associated with this simplification is affine isomorphic to the EOF formulation. We determine the dimension of the polyhedron associated with the simplification, we briefly present a set of very simple facets and we introduce, analyse and demonstrate be a facet, some more complex inequalities. / O conceito de largura em Ãrvore (âtreewidthâ) foi introduzido por Robertson e Seymour. A largura em Ãrvore de um grafo G Ã o mÃnimo k tal que G pode ser decomposto em uma DecomposiÃÃo em Ãrvore (DEA) com cada subconjunto de vÃrtice com no mÃximo k+1 vÃrtices.
Resultados recentes demonstram que vÃrios problemas NP-Completos podem ser resolvidos em tempo polinomial, ou ainda linear, quando restritos a grafos com largura em Ãrvore pequena.
Em nossa pesquisa bibliogrÃfica, focamos a atenÃÃo no cÃlculo de limites inferiores para a largura em Ãrvore e descrevemos, em nossa dissertaÃÃo, alguns dos resultados jà disponÃveis na literatura.
NÃs percebemos que formulaÃÃes lineares-inteiras para a determinaÃÃo da largura em Ãrvore sÃo limitadas na literatura e nÃo hà estudos disponÃveis sobre os poliedros associados a elas.
A formulaÃÃo por ordem de eliminaÃÃo (EOF) foi proposta por Koster e Bodlaender. Ela à baseada na eliminaÃÃo ordenada de vÃrtices e na relaÃÃo entre a largura em Ãrvore de um grafo e suas cordalizaÃÃes.
Como resultado de nosso estudo, apresentamos uma simplificaÃÃo da formulaÃÃo EOF, demonstramos que o poliedro associado a simplificaÃÃo à afim-isomÃrfico ao da formulaÃÃo EOF, verificamos a dimensÃo do poliedro associado à simplificaÃÃo, apresentamos brevemente um rol de facetas muito simples desse poliedro e, em seguinte, introduzimos, analisamos e demonstramos ser faceta algumas desigualdades mais complexas.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:10419 |
| Date | 09 February 2015 |
| Creators | Jefferson LourenÃo Gurguri |
| Contributors | Victor Almeida Campos, Manoel Bezerra Campelo Neto, Ana Shirley Ferreira da Silva, Yuri Abitbol de Menezes Frota |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0016 seconds