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) Depends on
Dirección:
PABELLON 2 S/N, C1428EGA - Capital Federal - Argentina

Contacto:

Enviar Mensaje

Experticia en CyT*

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. *Información suministrada por el agente en SIGEVA

Líneas de Investigación

Teoría de Grafos Natural and exact sciences - Mathematics - Applied mathematics

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


Dirigida por
DURAN, GUILLERMO ALFREDO
Carrera Investigador

Producción CyT

Cargando datos . . .

Oferta Tecnológica

Cargando datos . . .