• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Polyhedral Study of Tree Decomposition / Estudo PoliÃdrico de DecomposiÃÃo em Ãrvore

Jefferson LourenÃo Gurguri 09 February 2015 (has links)
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.

Page generated in 0.1942 seconds