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

Internal doctoral fellowship

Speciality
Teoría de grafos
Scientific discipline
Mathematics - Mathematics
Topic
Structural characterizations of subclasses and variants of perfect graphs
Workplace
INSTITUTO DE CALCULO REBECA CHEREP DE GUBER (IC, CONICET-UBA)
Dependencies
Show more information Show less information
Address:
PABELLON 2 S/N, C1428EGA - Capital Federal - Argentina
Show map
Summary Information provided by the agent in 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.
Show more Show less
Lines of Investigation

Teoría de Grafos

Natural and exact sciences

  • Mathematics
  • Applied mathematics
Key Words
FORBIDDEN SUBRAPHSPERFECT GRAPHSALGORITMOS DE RECONOCIMIENTORECOGNITION ALGORITHMSSUBGRAFOS PROHIBIDOSGRAFOS PERFECTOS
Education

2016 - 2021

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

FACULTAD DE CIENCIAS EXACTAS Y NATURALES, UNIVERSIDAD DE BUENOS AIRES

HR Training
Directed by:
DURAN, GUILLERMO ALFREDO
Scientific Research Career at CONICET
DURAN, Guillermo Alfredo Scientific Research Career at CONICET
Loading section Science and Technology Production...
Loading section Services...
Contact
Send Message