GeraÃÃo de Facetas para Politopos de Conjuntos Independentes / Facet-generating Procedures for Stable Set Polytopes

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

26/09/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.

ASSUNTO(S)

ciencia da computacao conjunto independente subgrafo induzido k-partido combinatÃria poliÃdrica facetas lifting stable set induced k-partite subgraph polyhedral combinatorics facets lifting anÃlise combinatÃria teoria dos grafos otimizaÃÃo combinatÃria

ACESSO AO ARTIGO

Documentos Relacionados