Registro:
| Documento: | Tesis de Grado |
| Título: | Structural and algorithmic results on neighborhood-perfect graphs and neighborhood numbers |
| Autor: | Warnes, Xavier Sebastián |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Fecha de defensa: | 2014-11-20 |
| Fecha en portada: | Noviembre 2014 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias Matemáticas |
| Departamento Docente: | Departamento de Matemáticas |
| Director: | Safe, Martín Darío |
| Director Asistente: | Durán, Guillermo Alfredo |
| Jurado: | Bonomo, Flavia; Perrucci, Daniel Roberto |
| Idioma: | Inglés |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/seminario_nMAT000873_Warnes |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000873_Warnes.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nMAT000873_Warnes |
| Ubicación: | Dep.MAT 000873 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Warnes, Xavier Sebastián. (2014). Structural and algorithmic results on neighborhood-perfect graphs and neighborhood numbers. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/seminario_nMAT000873_Warnes |
Resumen:
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.
Abstract:
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.
Citación:
---------- APA ----------
Warnes, Xavier Sebastián. (2014). Structural and algorithmic results on neighborhood-perfect graphs and neighborhood numbers. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nMAT000873_Warnes
---------- CHICAGO ----------
Warnes, Xavier Sebastián. "Structural and algorithmic results on neighborhood-perfect graphs and neighborhood numbers". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2014.https://hdl.handle.net/20.500.12110/seminario_nMAT000873_Warnes
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nMAT000873_Warnes.pdf
Distrubución geográfica
