Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König

Mostrar todas las versiones(3)

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 pr...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Safe, Martín Darío
Formato: Tesis Doctoral
Lenguaje:Inglés
Publicado: 2011
Materias:
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
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n4969_Safe
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n4969_Safe
record_format dspace
spelling todo:tesis_n4969_Safe2023-10-03T12:52:21Z Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König On structural characterizations of graph classes related to perfect graphs and the König property Safe, Martín Darío 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 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. A graph is balanced if its clique-matrix contains no edge-vertex incidence matrix of an odd cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs was given, no such characterization by minimal forbidden induced subgraphs is known. In this thesis, we prove minimal forbidden induced subgraph characterizations of balanced graphs, restricted to graphs that belong to certain graph classes. We also show that, within some of these classes, our characterizations lead to linear-time recognition algorithms for balancedness. A graph is clique-perfect if, in each induced subgraph, the minimum size of a set of vertices meeting all the cliques equals the maximum number of vertex-disjoint cliques. Unlike perfect graphs, neither a forbidden induced subgraph characterization nor the complexity of the recognition problem are known for clique-perfect graphs. In this thesis, we characterize clique-perfect graphs by means of forbidden induced subgraphs within two different graph classes, which imply polynomial-time recognition algorithms for clique-perfectness within the same two graph classes. A graph has the Kőnig property if the minimum number of vertices needed to meet every edge equals the maximum size of a set of vertex-disjoint edges. In this thesis, we characterize these graphs by forbidden subgraphs, which, in its turn, allows us to characterize edge-perfect graphs by forbidden edge-subgraphs. Fil: Safe, Martín Darío. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2011 Tesis Doctoral PDF Inglés info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n4969_Safe
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv Inglés
topic 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
spellingShingle 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
Safe, Martín Darío
Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König
topic_facet 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
description 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.
format Tesis Doctoral
author Safe, Martín Darío
author_facet Safe, Martín Darío
author_sort Safe, Martín Darío
title Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König
title_short Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König
title_full Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König
title_fullStr Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König
title_full_unstemmed Sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de König
title_sort sobre caracterizaciones estructurales de clases de grafos relacionadas con los grafos perfectos y la propiedad de könig
publishDate 2011
url https://hdl.handle.net/20.500.12110/tesis_n4969_Safe
work_keys_str_mv AT safemartindario sobrecaracterizacionesestructuralesdeclasesdegrafosrelacionadasconlosgrafosperfectosylapropiedaddekonig
AT safemartindario onstructuralcharacterizationsofgraphclassesrelatedtoperfectgraphsandthekonigproperty
_version_ 1782028991680479232

Ejemplares similares