1. CONICET
  2. Comunidad CONICET
  3. LUCÍA BUSOLINI
Comunidad CONICET
BUSOLINI, LUCÍA

Beca interna doctoral

Especialidad
Teoría de grafos
Disciplina Científica
Matemática - Matemática
Tema
Caracterizaciones estructurales de subclases y variantes de los grafos perfectos
Lugar de Trabajo
INSTITUTO DE CALCULO REBECA CHEREP DE GUBER (IC, CONICET-UBA)
Depende de
Ver más información Ver menos información
Dirección:
PABELLON 2 S/N, C1428EGA - Capital Federal - Argentina
Ver mapa
Resumen Información suministrada por el agente en SIGEVA
Un grafo es perfecto cuando, en todos sus subgrafos inducidos, el número cromático (número mínimo de colores necesario para colorear los vértices de modo que vértices adyacentes reciban colores distintos) coincide con el número clique (tamaño máximo de una clique). Los grafos perfectos han despertado mucho interés, por ejemplo, debido a que importantes problemas que son NP-completos para la clase general de los grafos (por ejemplo, coloreo, clique máxima y conjunto independiente máximo) se han ... Un grafo es perfecto cuando, en todos sus subgrafos inducidos, el número cromático (número mínimo de colores necesario para colorear los vértices de modo que vértices adyacentes reciban colores distintos) coincide con el número clique (tamaño máximo de una clique). Los grafos perfectos han despertado mucho interés, por ejemplo, debido a que importantes problemas que son NP-completos para la clase general de los grafos (por ejemplo, coloreo, clique máxima y conjunto independiente máximo) se han probado resolubles en tiempo polinomial.Hace un par de décadas, se probó una caracterización por subgrafos prohibidos para esta clase de grafos y se encontró un algoritmo polinomial para reconocerlos.Mi trabajo tiene como objetivo encontrar caracterizaciones estructurales de diferentes subclases y variantes de los grafos perfectos y explotar dichas caracterizaciones para el desarrollo de algoritmos eficientes. Para eso, además de conocer los avances previos sobre estos temas, es necesario saber sobre estructuras de datos y complejidad algorítmica.
Ver más Ver menos
Líneas de Investigación

Teoría de Grafos

Ciencias naturales y exactas

  • Matemáticas
  • Matemática aplicada
Palabras Clave
FORBIDDEN SUBRAPHSPERFECT GRAPHSALGORITMOS DE RECONOCIMIENTORECOGNITION ALGORITHMSSUBGRAFOS PROHIBIDOSGRAFOS PERFECTOS
Formación Académica

2016 - 2021

Licenciada en Ciencias Matemáticas (orientación pura)

FACULTAD DE CIENCIAS EXACTAS Y NATURALES, UNIVERSIDAD DE BUENOS AIRES

Formación de RRHH
Dirigida por:
DURAN, GUILLERMO ALFREDO
Carrera Investigador
DURAN, Guillermo Alfredo Carrera Investigador
Cargando sección Producción CyT...
Cargando sección Oferta Tecnológica...
Contacto
Enviar Mensaje