Descripción: Los problemas de dominación forman un área de investigación en crecimiento, debidoa la cantidad de aplicaciones que pueden modelar, entre las cuales podemos nombrarredes sociales, sistemas distribuidos, redes biológicas, problemas de localización deinstalaciones, etc. En esta tesis estudiamos los siguientes problemas de dominación (i) el conjunto dominante mínimo, (ii) dominación romana, (iii) dominación eficientepor vértices, (iv) dominación eficiente por aristas (también conocida como matchinginducido dominante), (v) dominación perfecta por vértices (vi) dominación perfectapor aristas, y (vii) subgrafo cordal máximo inducido sin vertices propiamentedominados (también conocido como eliminación de vértices para formar clusters). Para el problema (i) determinamos su complejidad para clases de grafos donde seprohiben subgrafos inducidos con a lo sumo cuatro vértices. Estudiamos los problemas (i) y (ii) para varias subclases de grafos P5-free, dando algoritmos eficientes, robustos ysimples en ambos casos. Algoritmos de complejidad lineal para grafos arco-circularesfueron presentados para los problemas (iv), (v), (vi) usando algoritmos existentespara el problema (iii). Damos tres algoritmos de tiempo exponencial para resolverel problema (iv) en grafos generales. Además, para el problema (iv), presentamosalgoritmos de complejidad O(n) restringidos a grafos cordales, dualmente-cordales, biconvexos,y claw-free. Estudiamos cuatro variantes del problema (vii) y presentamosalgoritmos eficientes para todos ellos cuando nos restringimos a grafos de intervalospropios, grafos de intervalos, grafos arco-circulares, grafos de permutación, y grafostrapezoide. Por otro lado, probamos que las cuatro variantes son NP-Dificil paragrafos bipartitos. Finalmente, mostramos que dos variantes son NP-Dificil para grafossplit, mientras que las otras dos variantes se pueden resolver en tiempo polinomial.

Descripción: Esta tesis está dedicada al estudio de representaciones por operadores acotados en espacios Lp del álgebra de Leavitt LQ de un grafo. Sean Q un grafo orientado finito por filas y LQ su álgebra de Leavitt sobre C. Parap ∈ [1,∞) consideramos la noción de representación espacial de LQ por operadores linealesy acotados en un espacio Lp(X, μ), que generaliza la introducida por N.C. Phillips par el casoen que Q es la rosa de d pétalos, y LQ el álgebra de Leavitt Ld. Para cada p consideramos la completación Op(Q) de LQ bajo la norma ||a|| := sup ρ espacial ||ρ(a)|| (a ∈ LQ). Probamos que si LQ es simple y ρ es una Lp representación espacial no nula de LQ entonces ||a||ρ := ||ρ(a)|| no depende de ρ. En particular si LQ es simple, Op(Q) = ρ(LQ) paracualquier representación espacial no nula ρ. Probamos que si Q y F son dos grafos finitos por filas, y p y q distintos, no existe unmorfismo continuo de Op(Q) en Oq(F). Probamos además que Op(Q) es simple si y sólo si LQ lo es. Aquí, una Lp álgebra deoperadores A se dice simple si todo morfismo no nulo de A en otra Lp álgebra de operadoreses inyectivo. Esta definición de simplicidad no coincide con la de álgebras de Banach, puespodrían existir ideales cerrados que no sean el núcleo de un morfismo contractivo entre Lpálgebras de operadores, al contrario de lo que sucede en el caso de C*-álgebras. Probamos que existe una biyección entre la clase de ideales S1 invariantes en Op(Q) yel conjunto de subconjuntos de vértices hereditarios y saturados de Q. Este resultado esun análogo a la biyección ya conocida entre ideales graduados del álgebra de Leavitt y lossubconjuntos de vértices hereditarios y saturados. Para Q finito por filas arbitrario, calculamos la K-teoría topológica de Op(Q) y probamosque coincide con la de la C*-álgebra de Cuntz-Krieger de Q.

Descripción: En este trabajo se estudian dos problemas de ruteo de vehículos: el Problema de Recolección y Entrega Punto a Punto con Distancias Asimétricas (APDP, por sus siglas en inglés) y el Problema de Recolección y Entrega Punto a Punto con Distancias Asimétricas e Incompatibilidades (PDPwI), una variante del primero a ́un no descripta en la bibliografía. Se presenta un estudio sobre la efectividad computacional de distintas formulaciones para resolver el APDP. Uno de los modelos evaluados es original, mientras que los restantes fueron tomadas de la bibliografía. De estos, algunos fueron pensados inicialmente para este problema y la amplia mayoría fueron ideados para el Problema del Viajante de Comercio con Restricciones de Precedencia y Distancias Asimétricas que, aunque lo generaliza, sus formulaciones no habían sido aún usadas para resolver al APDP. En cuanto al PDPwI, se lo define formalmente y se muestra que además de generalizar al APDP, generaliza el problema de coloreo de vértices, el Bin Packing Problem y el Bin Packing Problem with Conflicts. Se formulan tres diferentes modelos para el PDPwI basados en formulaciones que resultaron eficientes para el APDP. Se construye también un conjunto de instancias de prueba para el PDPwI y se lo utiliza para evaluar las tres formulaciones creadas mediante algoritmos Branch And Cut. En base a estas pruebas y otras consideraciones, se selecciona uno de estos modelos para el cual se realiza un estudio poliedral del politopo asociado, hallándose 36 familias de desigualdades y 5 de igualdades válidas. Asimismo se caracteriza la dimensión del mismo y se demuestra que una de las familias de desigualdades halladas define una faceta. En base a los análisis ya mencionados se desarrolla un algoritmo Branch And Cut, para el cuál también se crean algoritmos de planos de corte, una heurística primal y una estrategia de branching. Finalmente se muestra la efectividad de las componentes propuestas para el algoritmo mediante pruebas computacionales con el conjunto de instancias creadas.