Structural and algorithmic results on neighborhood-perfect graphs and neighborhood numbers
Un grafo es vecindad-perfecto si en cada subgrafo inducido, el mínimo número de vecindades cerradas necesarias para cubrir los vértices y aristas es igual al máximo cardinal de un conjunto de vértices y aristas sin dos elementos pertenecientes a la misma vecindad cerrada. A diferencia de los grafos...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , , |
| Formato: | Tesis Libro |
| Lenguaje: | Inglés |
| Publicado: |
Noviembre 2014
|
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 03804nam a22003377a 4500 | ||
|---|---|---|---|
| 003 | AR-BaUEN | ||
| 005 | 20251017172333.0 | ||
| 008 | 251017s2014 ag ad||f|m||| 00| 0|eng|d | ||
| 040 | |a AR-BaUEN |b spa |c AR-BaUEN | ||
| 041 | 0 | |b spa |b eng | |
| 044 | |a ag | ||
| 084 | |a MAT 000873 | ||
| 100 | 1 | |a Warnes, Xavier Sebastián | |
| 245 | 1 | 0 | |a Structural and algorithmic results on neighborhood-perfect graphs and neighborhood numbers |
| 260 | |c Noviembre 2014 | ||
| 300 | |a x, 105 p. : |b il., gráfs. | ||
| 502 | |b Licenciado en Ciencias Matemáticas |c Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |d 2014-11-20 | ||
| 506 | |2 openaire | ||
| 518 | |o Fecha de publicación en la Biblioteca Digital FCEN-UBA | ||
| 520 | 3 | |a Un grafo es vecindad-perfecto si en cada subgrafo inducido, el mínimo número de vecindades cerradas necesarias para cubrir los vértices y aristas es igual al máximo cardinal de un conjunto de vértices y aristas sin dos elementos pertenecientes a la misma vecindad cerrada. A diferencia de los grafos perfectos, los grafos vecindad-perfectos no han sido aún caracterizados por subgrafos inducidos prohibidos, ni tampoco se conoce la complejidad algorítmica del problema de reconocimiento de la clase. En esta tesis probamos caracterizaciones de los grafos vecindad-perfectos por subgrafos inducidos prohibidos minimales restringidas a ciertas clases de grafos, incluyendo la clase de los grafos P4-tidy, la de los tree-cographs y ciertas clases relacionadas a los grafos clique-Helly hereditarios. Por otro lado consideramos el problema de reconocimiento de los grafos vecindad-perfectos y encontramos algoritmos polinomiales para resolverlo restringido a distintas clases de grafos. Finalmente mostramos dos algoritmos lineales para encontrar los parámetros involucrados en la definición de vecindad-perfección (y los conjuntos óptimos que realizan los parámetros) restringiendo la entrada a grafos pertenecientes a la clases de los grafos P4-tidy y los tree-cographs, y probamos que el problema de determinar estos mismos parámetros es NP-completo aún para grafos complemento de bipartito. |l spa | |
| 520 | 3 | |a A graph is neighborhood-perfect if for every induced subgraph, the minimum number of closed neighborhoods needed to cover all the vertices and edges equals the maximum size of a set of vertices and edges, no two of which belong to the same closed neighborhood. Unlike perfect graphs, neither a forbidden induced subgraph characterization, nor the computational complexity of the recognition problem are known for the whole class of neighborhood-perfect graphs. In this thesis we give characterizations of neighborhood-perfect graphs by minimal forbidden induced subgraphs restricted to several graph classes, including the classes of the P4-tidy graphs, tree-cographs and several graph classes related to the class of hereditary clique-Helly graphs. Moreover we consider the problem of recognizing neighborhood-perfect graphs and propose polynomial-time algorithms to solve it restricted to different graph classes. Finally we present two linear-time algorithms to find the parameters involved in the definition of neighborhood-perfectness for P4-tidy graphs and tree-cographs and prove that the problems of these same parameters are NP-complete when restricted to complement of bipartite graphs. |l eng | |
| 540 | |2 cc |f https://creativecommons.org/licenses/by-nc-sa/2.5/ar | ||
| 700 | 1 | |a Safe, Martín Darío | |
| 700 | 1 | |a Durán, Guillermo Alfredo | |
| 700 | 1 | |a Bonomo, Flavia | |
| 700 | 1 | |a Perrucci, Daniel Roberto | |
| 856 | 4 | |q application/pdf | |
| 931 | |a DM | ||
| 961 | |b seminario |c PR |e ND | ||
| 962 | |a info:ar-repo/semantics/tesis de grado |a info:eu-repo/semantics/bachelorThesis |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 108576 | ||