Resumen:
Los grafos perfectos fueron definidos por Berge en 1961. Un grafo se dice perfecto cuando para todo subgrafo inducido coinciden el número cromático y el tamaño de una clique máxima. Los grafos perfectos son de gran interés desde el punto de vista algorítmico ya que para esta clase los problemas clásicos de optimización pueden resolverse en tiempo polinomial. A partir de esta clase se han definido y estudiado una gran cantidad de variantes de los mismos, entre ellas algunas que también se definen por la igualdad de 2 parámetros, como ser los grafos clique-perfectos, los grafos coordinados y los grafos vecindad-perfectos. Para estas clases una caracterización por subgrafos inducidos prohibidos no es conocida y para algunas de ellas también se desconoce la complejidad de su reconocimiento. En este trabajo se realizó un completo estado del arte de los grafos perfectos, que incluye las caracterizaciones estructurales conocidas como Teorema Débil y Teorema Fuerte -ambas conjeturadas por Berge pero demostradas en los años 1972 y 2002 respectivamente-, y algoritmos de reconocimiento polinomiales para esta clase. Se estudiaron además los avances parciales realizados en la misma dirección para las tres variaciones nombradas anteriormente.
Citación:
---------- APA ----------
Pardal, Nina. (2015). Un estado del arte acerca de grafos perfectos y algunas variaciones. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000711_Pardal
---------- CHICAGO ----------
Pardal, Nina. "Un estado del arte acerca de grafos perfectos y algunas variaciones". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2015.https://hdl.handle.net/20.500.12110/seminario_nMAT000711_Pardal
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000711_Pardal.pdf
Distrubución geográfica
