Título: Estudio del operador biclique aplicado a distintas clases de grafos

Director: Marina Groshaus

Jurados:
– Dra. Flavia Bonomo (UBA)

– Dr. Pablo de Caria (UNLP)

– Dr. Luerbio Faria (UERJ/Brasil)

Resumen:

Una biclique en un grafo es un subgrafo inducido bipartito completo maximal.  El estudio de las bicliques  ha recibido mucha atención en los últimos tiempos.   El grafo  biclique de  G, KB(G),  es el  grafo de intersección   de  las   bicliques  de   G.   Este   fue  definido   y caracterizado recientemente. Sin embargo,  aún sigue abierta  la pregunta  sobre la existencia  de un algoritmo eficiente que resuelva el problema de reconocimiento de grafos biclique.  En  esta tesis  estudiamos el  problema de  reconocimiento de
grafos  biclique de  algunas clases  de grafos.   Se pretende  con esto, acercarse al problema  de reconocimiento de grafos  biclique en general, encontrando clases  donde el problema  de decidir  si un grafo  es grafo biclique sea  polinomial o se  pueda probar que es  NP-completo.  Entre otras, en  este trabajo estudiamos  el operador biclique aplicado  a los grafos bipartitos cordales, split  y bipartitos de permutación.  También estudiamos el problema de reconocimiento de la clase biclique inversa de los  grafos completos,  es decir,  dado un  grafo, decidir  si su  grafo biclique  es completo.   Cabe mencionar  que,  dado que  la cantidad  de bicliques de  un grafo  puede ser exponencial,  no siempre  es eficiente
construir el grafo biclique para responder esta pregunta.

Palabras claves: Bicliques, cordal, grafo biclique, grafo clique, permutación, split.