Acerca de los gráficos de intervalos representados como intersecciones de rutas de tamaño unitario en formato ⌞

Vol 56, 2024 - 309692
Trabalho completo (Oral)
Favoritar este trabajo
¿Cómo citar este artículo?
Resúmenes

Los gráficos EPG representan la clase de gráficos de intersección de bordes de rutas en una cuadrícula, siendo EPG el acrónimo de "Rutas de intersección de bordes en una cuadrícula". El estudio de estos grafos comenzó en 2009 y, desde entonces, se han obtenido varios resultados sobre la complejidad de reconocer sus subclases. Los grafos ⌞-EPG son una subclase de los grafos EPG, en los que cada ruta puede tomar la forma de "⌞", además de los segmentos "−" y "|". Se ha demostrado que la complejidad de reconocer esta subclase es NP-completa, [Cameron et al., 2016]. Los grafos EPG de ⌞ unidades son una subclase de los grafos ⌞-EPG, en los que todos los segmentos de ruta son de talla única. En este artículo, además de definir la clase de grafo ⌞-unidad EPG, nos centramos en la clase de grafo de intervalo, para la cual proporcionamos una caracterización de subgrafo prohibida para grafos de intervalo que son EPG de ⌞ unidad.

¡Comparte tus ideas o preguntas con los autores!

¿Sabías que el mayor estímulo en el desarrollo científico y cultural es la curiosidad? ¡Deje sus preguntas o sugerencias al autor!

Inicia sesión para interactuar

¿Tiene alguna pregunta o sugerencia? ¡Comparte tus comentarios con los autores!

Instituciones
  • 1 Universidade Federal Fluminense (UFF)
Eje Temático
  • 19. TAG – Teoria e Algoritmos em Grafos
Palabras Clave
⌞-EPG unitaria
Caracterización por subgrafos prohibidos
Complejidad computacional