Repositorio Institucional
Repositorio Institucional
CONICET Digital
  • Inicio
  • EXPLORAR
    • AUTORES
    • DISCIPLINAS
    • COMUNIDADES
  • Estadísticas
  • Novedades
    • Noticias
    • Boletines
  • Ayuda
    • General
    • Datos de investigación
  • Acerca de
    • CONICET Digital
    • Equipo
    • Red Federal
  • Contacto
JavaScript is disabled for your browser. Some features of this site may not work without it.
  • INFORMACIÓN GENERAL
  • RESUMEN
  • ESTADISTICAS
 
Artículo

Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs

Alcón, Liliana GracielaIcon ; Bonomo, FlaviaIcon ; Mazzoleni, María PíaIcon
Fecha de publicación: 07/2017
Editorial: Springer Tokyo
Revista: Graphs And Combinatorics
ISSN: 0911-0119
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:
Matemática Pura

Resumen

We investigate graphs that can be represented as vertex intersections of horizontal and vertical paths in a grid, the so called B0-VPG graphs. Recognizing this class is an NP-complete problem. Although, there exists a polynomial time algorithm for recognizing chordal B0-VPG graphs. In this paper, we present a minimal forbidden induced subgraph characterization of B0-VPG graphs restricted to block graphs. As a byproduct, the proof of the main theorem provides an alternative certifying recognition and representation algorithm for B0-VPG graphs in the class of block graphs.
Palabras clave: Block Graphs , Forbidden Induced Subgraphs , Paths on A Grid , Vertex Intersection Graphs
Ver el registro completo
 
Archivos asociados
Thumbnail
 
Tamaño: 775.0Kb
Formato: PDF
.
Descargar
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/57004
DOI: https://dx.doi.org/10.1007/s00373-017-1791-6
URL: https://link.springer.com/article/10.1007%2Fs00373-017-1791-6
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos(ICC)
Articulos de INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Alcón, Liliana Graciela; Bonomo, Flavia; Mazzoleni, María Pía; Vertex Intersection Graphs of Paths on a Grid: Characterization Within Block Graphs; Springer Tokyo; Graphs And Combinatorics; 33; 4; 7-2017; 653-664
Compartir
Altmétricas
 

Enviar por e-mail
Separar cada destinatario (hasta 5) con punto y coma.
  • Facebook
  • X Conicet Digital
  • Instagram
  • YouTube
  • Sound Cloud
  • LinkedIn

Los contenidos del CONICET están licenciados bajo Creative Commons Reconocimiento 2.5 Argentina License

https://www.conicet.gov.ar/ - CONICET

Inicio

Explorar

  • Autores
  • Disciplinas
  • Comunidades

Estadísticas

Novedades

  • Noticias
  • Boletines

Ayuda

Acerca de

  • CONICET Digital
  • Equipo
  • Red Federal

Contacto

Godoy Cruz 2290 (C1425FQB) CABA – República Argentina – Tel: +5411 4899-5400 repositorio@conicet.gov.ar
TÉRMINOS Y CONDICIONES