Catálogo de publicaciones - tesis
Título de Acceso Abierto
Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König
Martín Darío Safe Flavia Bonomo Guillermo Alfredo Durán
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
Un grafo es balanceado si su matriz clique no contiene como submatriz ninguna matriz de incidencia arista-vértice de un ciclo impar. Se conoce una caracterización para estos grafos por subgrafos inducidos prohibidos, pero ninguna que sea por subgrafos inducidos prohibidos minimales. En esta tesis probamos caracterizaciones por subgrafos inducidos prohibidos minimales para los grafos balanceados restringidas a ciertas clases de grafos y mostramos que dentro de algunas de ellas conducen a algoritmos lineales para reconocer el balanceo. Un grafo es clique-perfecto si en cada subgrafo inducido el mínimo número de vértices que intersecan todas las cliques coincide con el máximo número de cliques disjuntas dos a dos. Contrariamente a los grafos perfectos, para estos grafos no se conoce una caracterización por subgrafos inducidos prohibidos ni la complejidad del problema de reconocimiento. En esta tesis caracterizamos los grafos clique-perfectos por subgrafos inducidos prohibidos dentro de dos clases de grafos, lo que implica algoritmos de reconocimiento polinomiales para la clique-perfección dentro de dichas clases. Un grafo tiene la propiedad de Kőnig si el mínimo número de vértices que intersecan todas las aristas iguala al máximo número de aristas que no comparten vértices. En esta tesis caracterizamos estos grafos por subgrafos prohibidos, lo que nos permite también caracterizar los grafos arista-perfectos por arista-subgrafos prohibidos.Palabras clave – provistas por el repositorio digital
ALGORITMOS DE RECONOCIMIENTO; GRAFOS ARCO-CIRCULARES; GRAFOS ARISTA-PERFECTOS; GRAFOS BALANCEADOS; GRAFOS BIPARTITOS; GRAFOS CLIQUE-HELLY HEREDITARIOS; GRAFOS CLIQUE-PERFECTOS; PROPIEDAD DE KÖNIG; GRAFOS COORDINADOS; GRAFOS DE LINEA; GRAFOS K-PERFECTOS HEREDITARIOS; GRAFOS PERFECTOS; SUBGRAFOS PROHIBIDOS; BALANCED GRAPHS; BIPARTITE GRAPHS; CIRCULAR-ARC GRAPHS; CLIQUE-PERFECT GRAPHS; COORDINATED GRAPHS; EDGE-PERFECT GRAPHS; FORBIDDEN SUBGRAPHS; KÖNIG PROPERTY; HEREDITARY CLIQUE-HELLY GRAPHS; HEREDITARY K-PERFECT GRAPHS; LINE GRAPHS; PERFECT GRAPHS; RECOGNITION ALGORITHMS
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2011 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2011
Información sobre licencias CC
