Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/16968
Título: Geração de Facetas para Politopos de Conjuntos Independentes
Título em inglês: Facet-generating Procedures for Stable Set Polytopes
Autor(es): Xavier, Alinson Santos
Orientador(es): Campelo Neto , Manoel Bezerra
Palavras-chave: Ciência da computação
Conjunto independente
Subgrafo induzido k-partido
Combinatória poliédrica
Facetas
Lifting
Stable set
Induced k-partite subgraph
Polyhedral combinatorics
Facets
Análise combinatória
Teoria dos grafos
Otimização combinatória
Data do documento: 2011
Citação: XAVIER, A. S. (2011)
Resumo: Um conjunto independente de um grafo é um subconjunto de vértices que não contém nenhum par de vértices vizinhos. O problema do maior conjunto independente consiste em encontrar um conjunto independente de cardinalidade máxima. O problema do maior subgrafo induzido k-partido consiste em encontrar k conjuntos independentes cuja união tenha cardinalidade máxima. Além de possuírem aplicação em diversas áreas, como visão computacional, biologia molecular e projeto de circuitos integrados, estes problemas também modelam outros problemas de otimização combinatória, como empacotamento de conjuntos e coloração de vértices. Neste trabalho, estudamos os politopos associados aos dois problemas. Primeiro, descrevemos um novo procedimento de geração de facetas para o politopo de conjuntos independentes, que unifica e generaliza diversos procedimentos anteriores. Além de gerar várias classes de desigualdades indutoras de facetas já conhecidas, este procedimento também gera novas desigualdades que ainda não foram descritas na literatura. Em seguida, estudamos o politopo do subgrafo induzido k-partido associado à formulação por representantes de cor. Identificamos suas facetas mais simples, mostramos que facetas podem ser geradas a partir de subgrafos induzidos, e descrevemos duas classes de subgrafos que geram facetas deste politopo. Para obter os principais resultados desta dissertação, fazemos um estudo da relação de afim-isomorfismo entre poliedros, e desenvolvemos um novo procedimento de conversão de faces em facetas que generaliza as diversas versões do procedimento de levantamento de variáveis.
Abstract: A stable set of a graph is a set of pairwise non-adjacent vertices. The maximum stable set problem is to find a stable set of maximum cardinality in a given graph. The maximum induced k-partite subgraph problem is to find k stable sets such that their union has maximum cardinality. Besides having applications in various fields, including computer vision, molecular biology and VLSI circuit design, these problems also model other important combinatorial problems, such as set packing and vertex coloring. In the present work, we study the facial structure of the polytopes associated with both problems. First, we describe a new facet generating procedure for the stable set polytope, which unifies and subsumes several previous procedures. Besides generating many well-known facet inducing inequalities, this procedure can also generate new facet-inducing inequalities which have not been previously described. Then, we study the maximum induced k-partite polytope formulated by asymmetric representatives. We describe its simplest facets, show that some of its facets arise from vertex induced subgraphs, and identify two classes of subgraphs which generate facets of the polytope. To reach these main results, we study the affine equivalence between polyhedra, and also develop a new facet generating procedure for general polyhedra which subsumes the many versions of the lifting of variables.
Descrição: XAVIER, Alinson Santos. Geração de Facetas para Politopos de Conjuntos Independentes. 2011. 141 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011.
URI: http://www.repositorio.ufc.br/handle/riufc/16968
Aparece nas coleções:DCOMP - Teses defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2011_dis_asxavier.pdf1,07 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.