Registro:
Documento: | Tesis Doctoral |
Disciplina: | computacion |
Título: | Métodos algebraicos para problemas discretos |
Título alternativo: | Algebraic methods for discrete problems |
Autor: | Tobis, Enrique Augusto |
Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
Lugar de trabajo: | Universidad de Buenos Aires - Facultad de Ciencias Exactas - Departamento de Matematica
|
Publicación en la Web: | 2010-03-09 |
Fecha de defensa: | 2009 |
Fecha en portada: | 2009 |
Grado Obtenido: | Doctorado |
Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
Departamento Docente: | Departamento de Computación |
Director: | Dickenstein, Alicia Marcela |
Consejero: | Becher, Verónica Andrea |
Jurado: | Villareal Rodriguez, R.; Sabia, J.; Chin Lin, M. |
Idioma: | Inglés |
Palabras clave: | GRAFO; CONJUNTO PARCIALMENTE ORDENADO; CONJUNTO INDEPENDIENTE; ANTICADENA; SERIE DE HILBERT; GRAFO DE BRUIJN; ETIQUETAMIENTO ADITIVO DE ARISTAS; ETIQUETAMIENTO ADITIVO DE VERTICES; COMPLEJIDADGRAPH; POSET; INDEPENDENT SET; ANTICHAIN; HILBERT SERIES; DE BRUIJN GRAPH; ADDITIVE EDGE LABELING; ADDITIVE VERTEX LABELING; COMPLEXITY |
Tema: | computación/teoría de grafos
|
Formato: | PDF |
Handle: |
http://hdl.handle.net/20.500.12110/tesis_n4555_Tobis |
PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n4555_Tobis.pdf |
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n4555_Tobis |
Ubicación: | COM 004555 |
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. Tobis, Enrique Augusto. (2009). Métodos algebraicos para problemas discretos. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n4555_Tobis |
Resumen:
En esta tesis estudiamos tres problemas que relacionan Teoría de Grafos y Álgebra. En particular, consideramos el problema de contar el número de conjuntos independientes en un grafo, así como el problema relacionado de contar el número de anticadenas en un conjunto parcialmente ordenado, desde la perspectiva del álgebra computacional. También describimos los conjuntos independientes máximos de los grafos de de Bruijn B(d; 3), vía el estudio de la acción del grupo simétrico en d elementos. Además, determinamos todos los etiquetamientos aditivos de aristas y de vértices módulo d en un grafo, por medio de una traducción combinatoria de los correspondientes problemas de álgebra lineal sobre el anillo de enteros módulo d.
Abstract:
In this thesis we study three problems that link Graph Theory and Algebra. In particular, we consider the problem of counting independent sets in a graph, as well as the related problem of counting antichains in a finite partially ordered set, from the perspective of computational algebra. We also completely describe the maximum independent sets of the de Bruijn graphs B(d; 3), via the study of the action of the symmetric group on d elements. Moreover, we determine all additive edge and vertex labelings modulo d on a graph, by combinatorially translating the corresponding linear algebra problems over the ring of integers modulo d.
Citación:
---------- APA ----------
Tobis, Enrique Augusto. (2009). Métodos algebraicos para problemas discretos. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n4555_Tobis
---------- CHICAGO ----------
Tobis, Enrique Augusto. "Métodos algebraicos para problemas discretos". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2009.https://hdl.handle.net/20.500.12110/tesis_n4555_Tobis
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n4555_Tobis.pdf