Grafos vértice intersección de caminos en una grilla: caracterización dentro de la clase de los grafos bloque.

LILIANA ALCÓN; FLAVIA BONOMO; MARÍA PÍA MAZZOLENI

Bahía Blanca

Congreso; LXV Reunión Anual de Comunicaciones Científicas; 2016

Investigamos los grafos que pueden ser representados como intersección por vértices de caminos horizontales o verticales en una grilla, conocidos como grafos B0-VPG. Reconocer a esta clase de grafos es un problema NP-completo. Aunque, existe un algoritmo polinomial para reconocer a los grafos Cordales B0-VPG. En este trabajo, presentamos una caracterización por subgrafos inducidos prohibidos minimales de los grafos B0-VPG restringidos a los grafos bloque. La demostración del teorema principal provee un algoritmo de reconocimiento alternativo para los grafos B0-VPG dentro de la clase de los grafos bloque.