Por favor, use este identificador para citar o enlazar este ítem: http://bibdigital.epn.edu.ec/handle/15000/4940
Título : Indices N y N+ para el polítopo de conjuntos estables asociado a ciertas familias de antiwebs
Autor : Montenegro Chingal, Jessica Maribel
Palabras clave : TEORIA POLIEDRAL
OPTIMIZACION COMBINATORIA
TEORIA DE GRAFOS
Fecha de publicación : 11-sep-2012
Editorial : QUITO: 2012.
Resumen : El polítopo de conjuntos estables ha sido ampliamente estudiado desde el enfoque de la teoría poliedral. En particular, el rango de Chvátal de es un tópico que ha recibido atención en años recientes. Considerando una clase específica de grafos llamada antiwebs , los trabajos de Holm et. al "On the Chvátal-rank of linear relaxations of the stable set polytope" y "A lower bound on the Chvátal-rank of antiwebs" encuentran cotas superiores e inferiores para el rango de Chvátal de las relajaciones de arista y de clique . En este proyecto hemos estudiado otro de los métodos clásicos para la generación de planos cortantes, propuesto por Lovász y Schrijver (1991), y su aplicación a . Hemos estudiado los índices N y N+ de , los cuales pueden ser considerados como conceptos análogos al rango de Chvátal. Demostramos que el índice N+ de es 1 y presentamos además una construcción que genera cotas superiores para el índice N de aplicable a ciertas familias de antiwebs.
URI : http://bibdigital.epn.edu.ec/handle/15000/4940
Aparece en las colecciones: Tesis Matemáticas (MAT)

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
CD-4472.pdfTesis completa628,49 kBAdobe PDFVisualizar/Abrir


Este ítem está protegido por copyright original



Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.