Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König

On structural characterizations of graph classes related to perfect graphs and the König property

dc.contributorBonomo, Flavia
dc.contributorDurán, Guillermo Alfredo
dc.creatorSafe, Martín Darío
dc.date2011
dc.date.accessioned2017-01-24T19:45:22Z
dc.date.available2017-01-24T19:45:22Z
dc.identifierhttp://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_4969_Safe
dc.identifierhttp://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=HASH01722591e20cafd3a1aac2f5
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/74789
dc.descriptionUn grafo es balanceado si su matriz clique no contiene como submatriz ninguna matriz de incidencia arista-vértice de un ciclo impar. Se conoce una caracterización para estos grafos por subgrafos inducidos prohibidos, pero ninguna que sea por subgrafos inducidos prohibidos minimales. En esta tesis probamos caracterizaciones por subgrafos inducidos prohibidos minimales para los grafos balanceados restringidas a ciertas clases de grafos y mostramos que dentro de algunas de ellas conducen a algoritmos lineales para reconocer el balanceo. Un grafo es clique-perfecto si en cada subgrafo inducido el mínimo número de vértices que intersecan todas las cliques coincide con el máximo número de cliques disjuntas dos a dos. Contrariamente a los grafos perfectos, para estos grafos no se conoce una caracterización por subgrafos inducidos prohibidos ni la complejidad del problema de reconocimiento. En esta tesis caracterizamos los grafos clique-perfectos por subgrafos inducidos prohibidos dentro de dos clases de grafos, lo que implica algoritmos de reconocimiento polinomiales para la clique-perfección dentro de dichas clases. Un grafo tiene la propiedad de Kőnig si el mínimo número de vértices que intersecan todas las aristas iguala al máximo número de aristas que no comparten vértices. En esta tesis caracterizamos estos grafos por subgrafos prohibidos, lo que nos permite también caracterizar los grafos arista-perfectos por arista-subgrafos prohibidos.
dc.formattext; pdf
dc.languageInglés
dc.publisherFacultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
dc.subjectComputación / Teoría de Grafos
dc.subjectALGORITMOS DE RECONOCIMIENTO
dc.subjectGRAFOS ARCO-CIRCULARES
dc.subjectGRAFOS ARISTA-PERFECTOS
dc.subjectGRAFOS BALANCEADOS
dc.subjectGRAFOS BIPARTITOS
dc.subjectGRAFOS CLIQUE-HELLY HEREDITARIOS
dc.subjectGRAFOS CLIQUE-PERFECTOS
dc.subjectPROPIEDAD DE KÖNIG
dc.subjectGRAFOS COORDINADOS
dc.subjectGRAFOS DE LINEA
dc.subjectGRAFOS K-PERFECTOS HEREDITARIOS
dc.subjectGRAFOS PERFECTOS
dc.subjectSUBGRAFOS PROHIBIDOS
dc.titleSobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König
dc.titleOn structural characterizations of graph classes related to perfect graphs and the König property
dc.typeTesis


Este ítem pertenece a la siguiente institución