A graph where every vertex has three neighboring vertices is a cubic graph. An edge-coloring is an assignment of colors to the edges of a graph in such a way that the edges incident to a vertex have no repeated colors. An edge-coloring is optimal if it uses the minimum possible number of colors. Vizing's Theorem implies that an optimal edge-coloring of a cubic graph requires three or four colors. If three colors are enough, we call the edge-coloring a Tait-coloring. If four colors are needed, we call the graph a snark. Holyer proved that deciding wether a cubic graph is Tait-colorable is an NP-complete problem, therefore it is widely believed that it is a very difficult or intractable problem in the general case. Nevertheless, theory does not forbid efficient solutions in specific cases: this is called "breaking intractability". We describe an heuristic algorithm called CVD, for "Conflicting Vertex Displacement", which has a good empirical performance in random regular graphs. Also it allows us to check a conjecture by Biggs on "odd graphs" in instances with milions of vertices and edges, using moderately powerful computers. Snarks are relevant in graph theory: they appear often as minimal counterexamples of important conjectures, such as the Cycle Double Cover Conjecture (every bridgeless graph has a family of cycles such that every edge belongs to exactly two cycles of the family). In the analysis and synthesis of snarks, multipoles, "pieces" of cubic graphs with free ends that can be joined to each other, are often used. In a Tait-colored multipole, the number of equally colored free ends for each color and the total number of free ends have the same parity (the number of vertices of the multipole has this same parity, too). This result, known as the Parity Lemma, allows the interpretation of multipoles as logic gates and cubic graphs as logic circuits. This gives a very general way to construct snarks, based on logic circuits with no valid Boolean assignment, and allows us to relate the Tait-coloring of cubic graphs to integer factorization. In particular, we can construct snarks from prime numbers. A state of a multipole is the restriction of a Tait-coloring of the multipole to its free ends. If the set of states of a multipole is a non-empty subset of the set of states of another multipole with a larger number of vertices, we call the smaller multipole a reduction of the larger one. An irreducible multipole is a multipole with no reduction (an obvious example is a minimal multipole, that is, with no vertices or with a single vertex). The maximum number of vertices of an irreducible multipole as a function of its number (m) of free ends is denoted by v(m). Its behavior is well-known only for m<6, while there is a specific lower bound for v(6). We prove the irreducibility of multipoles having a tree, a forest or a cycle as their underlying graphs. This allows us to prove a linear lower bound for v(m), the first general result for this function. / Un graf on cada vèrtex té tres vèrtexs adjacents és un graf cúbic. Un aresta-acoloriment és una assignació de colors a les arestes d'un graf de tal manera que no es repeteixin colors en les arestes incidents a un mateix vèrtex. Un aresta-acoloriment és òptim si utilitza el mínim nombre possible de colors. El Teorema de Vizing implica que un aresta-acolorament òptim d'un graf cúbic requereix tres o quatre colors. Si tres colors són suficients, de l'aresta-acoloriment en diem Tait-acoloriment. Si fan falta quatre colors, diem que el graf és un snark. Holyer va demostrar que determinar si un graf cúbic és Tait-acolorible és un problema NP-complet, i per tant se suposa àmpliament que és un problema molt difícil o intractable en el cas general. Tanmateix, la teoria no prohibeix que es puguin resoldre eficientment casos concrets: és el que s'anomena "ruptura de la intractabilitat". Descrivim un algorisme heurístic anomenat DVC, per "Desplaçament de Vèrtexs Conflictius", que té un bon rendiment empíric en grafs regulars aleatoris. També ens permet comprovar una conjectura de Biggs sobre els "odd graphs" en instàncies de milions de vèrtexs i arestes, utilitzant ordinadors de potència moderada. Els snarks són rellevants en la teoria de grafs: sovint apareixen com a contraexemples minimals de conjectures importants, com per exemple la Conjectura del Recobriment Doble per Cicles (tot graf sense ponts té una família de cicles tal que cada aresta pertany exactament a dos dels cicles). En l'anàlisi i síntesi d'snarks se solen utilitzar multipols, que són "peces" de grafs cúbics amb extrems lliures que es poden unir entre ells. En un multipol Tait-acolorit, el nombre d'extrems lliures de cada color té la mateixa paritat que el nombre total d'extrems lliures (i que el nombre de vèrtexs del multipol). Aquest resultat, conegut com el Lema de Paritat, permet interpretar els multipols com a portes lògiques i els grafs cúbics com a circuits lògics. Això proporciona una manera molt general de construir snarks, en base a circuits lògics sense cap assignació booleana vàlida, i també permet relacionar l'aresta-acoloriment de grafs amb la factorització de nombres enters. En particular, permet construir snarks a partir de nombres primers. Un estat d'un multipol és la restricció d'un Tait-acoloriment del multipol als seus extrems lliures. Si el conjunt d'estats d'un multipol és un subconjunt no buit del conjunt d'estats d'un altre multipol amb un nombre de vèrtexs més gran, diem que n'és una reducció. Un multipol irreductible és un multipol sense cap reducció (un exemple obvi és un multipol minimal, és a dir sense vèrtexs o amb un sol vèrtex). El màxim nombre de vèrtexs d'un multipol irreductible en termes del seu nombre d'extrems lliures és una funció, representada per v(m), el comportament de la qual només es coneix exactament per m<6, mentre que hi ha una fita inferior específica per v(6). Demostrem la irreductibilitat dels multipols que tenen un arbre, un bosc o un cicle com a graf subjacent. Això ens permet establir una fita lineal inferior que és el primer resultat de naturalesa general sobre la funció v(m).

For a given cost matrix and a given communication requirement matrix, the OCSTP is defined as finding a spanning tree that minimizes the operational cost of the network. OCST can be used to design of more efficient communication and transportation networks, but appear also, as a subproblem, in hub location and sequence alignment problems. This thesis studies several mixed integer linear optimization formulations of the OCSTP and proposes a new one. Then, an efficient Branch & Cut algorithm derived from the Benders decomposition of one of such formulations is used to successfully solve medium-sized instances of the OCSTP. Additionally, two new combinatorial lower bounds, two new heuristic algorithms and a new family of spanning tree neighborhoods based on the Dandelion Code are presented and tested.

El fet que cada vegada disposem de més dades socials de sistemes socio-tecnològics---sistemes que registren la nostra activitat diària, tals com a registres de targeta de crèdit, registres de trucades telefòniques, correu electrònic, etc.---i les xarxes socials on-line---com facebook, twitter, instagram, etc.---, ha fet possible estudiar el comportament humà des de diferents perspectives. Descobrir els patrons darrere d'aquestes dades no només aportarà un millor coneixement de la societat, sinó que també beneficiaria a la societat en diferents aspectes, com l'adaptació de tecnologia a les necessitats socials o el disseny de millors polítiques per evitar la propagació d'epidèmies. L'objectiu d'aquesta tesi és precisament descobrir patrons estructurals i temporals en els sistemes socials i desenvolupar models predictius sobre la seva base. En particular, analitzem l'evolució a llarg termini en una xarxa de correu electrònic amb més d'1.000 persones al llarg de quatre anys consecutius. Veiem que, encara que l'evolució de la comunicació entre usuaris és altament impredictible, l'evolució macro de les xarxes de comunicació social segueix lleis estadístiques ben definides, caracteritzades pel decaïment exponencial de les variacions logarítmicas del pes de les comunicacions entre usuaris i del pes dels individus a la xarxa. Al mateix temps, trobem que els individus tenen una forma característica de comunicar-se, i aquesta no canvia en anys. Quant a la predictabilidad, desenvolupem dos models basats en xarxes: un model de recomanació (que prediu votacions d'usuaris sobre objectes) i un model d'inferència temporal (que prediu successos en el temps). El nostre model de recomanació és escalable i considerablement més precís en les seves prediccions que els algorismes actuals per bases de dades de milions de votacions. L'enfocament es basa en la suposició que hi ha grups de persones i d'articles (per exemple, pel·lícules, llibres, etc.) i que les preferències d'un individu sobre un element donat depenen del grups als que pertanyin. Però a més, permet que cada individu i cada article pertanyin simultàniament a diferents grups. Les comunitats superposades resultants i les prediccions sobre les votacions poden inferir-se amb un algorisme escalable de maximització d'expectatives basat en una aproximació variacional. En el mo / El hecho que cada vez dispongamos de más datos sociales de sistemas socio-tecnológicos---sistemas que registran nuestra actividad diaria, tales como registros de tarjeta de crédito, registros de llamadas telefónicas, correo electrónico, etc.---y las redes sociales on-line---como facebook, twitter, instagram, etc.---, ha hecho posible estudiar el comportamiento humano desde diferentes perspectivas. Descubrir los patrones detrás de estos datos no sólo aportará un mejor conocimiento de la sociedad, sino que también beneficiaría a la sociedad en diferentes aspectos, como la adaptación de la tecnología a las necesidades sociales o el diseño de mejores políticas para evitar la propagación de epidemias. El objetivo de esta tesis es precisamente descubrir patrones estructurales y temporales en los sistemas sociales y desarrollar modelos predictivos en base a ellos. En particular, analizamos la evolución a largo plazo en una red de correo electrónico con más de 1.000 personas a lo largo de cuatro años consecutivos. Vemos que, aunque la evolución de la comunicación entre usuarios es altamente impredecible, la evolución macro de las redes de comunicación social sigue leyes estadísticas bien definidas, caracterizadas por el decaimiento exponencial de las variaciones logarítmicas del peso de las comunicaciones entre usuarios y del peso de los individuos en la red. Así mismo, encontramos que los individuos presentan una forma caracteristica de comunicarse, y esta no cambia en años. En cuanto a la predictibilidad, desarrollamos dos modelos basados en redes: un modelo de recomendación (que predice votaciones de usuarios sobre objetos) y un modelo de inferencia temporal (que predice sucesos en el tiempo). Nuestro modelo de recomendación es escalable y considerablemente más preciso en sus predicciones que los algoritmos actuales para bases de datos de millones de votaciones. El enfoque se basa en la suposición de que hay grupos de personas y de artículos (por ejemplo, películas, libros, etc.) y que las preferencias de un individuo sobre un artículo dado dependen de los grupos a los que pertenezcan. Pero además, permitimos que cada individuo y cada artículo pertenecan simultáneamente a diferentes grupos. Las comunidades superpuestas resultantes y las predicciones sobre las votaciones pueden inferirse con un algoritmo de maximiz / The increasing availability of social data sources from socio-technological systems ---systems that record our daily activity such as credit card records, call-phone records, email, etc.--- and on-line social networks ---such as facebook, twitter, instagram, etc.---, has made it possible to study human behavior from different perspectives. Uncovering the patterns behind this data would not only give us a better knowledge about our society but could also benefit our society in a number of ways such as adapting technology to social needs or design better policies to avoid spread of epidemics. The aim of this thesis is precisely to uncover both structural and temporal patterns in social systems and to develop predictive models based on them. In particular, we analyze the long-term evolution in an email network with over 1,000 individuals throughout four consecutive years. We find that, although the evolution of individual ties is highly unpredictable, the macro-evolution of social communication networks follows well-defined statistical laws, characterized by exponentially decaying log-variations of the weight of social ties and of individuals' social strength. At the same time, we find that individuals have social signatures that are remarkably stable over the scale of several years. Regarding predictability, we develop two network-based models: a recommender model, and a temporal inference model. Our recommender model makes scalable predictions and is considerably more accurate than current algorithms for large datasets. The approach is based on the assumption that there are groups of individuals and of items (e.g. movies, books, etc.), and that the preferences of an individual for an given item depend on their group memberships. Importantly, we allow each individual and each item to belong simultaneously to different groups. The resulting overlapping communities and the predicted preferences can be inferred with a scalable expectation-maximization algorithm based on a variational approximation. In the temporal inference model users can belong simultaneously to different groups, but also the time intervals belong to overlapping communities. The results suggest that the algorithm is able to distinguish real events of non-events almost perfectly.

La majoria de metaheuristiques tenen una component aleatori, que normalment està basada en aleatorització uniforme -i.e., l'ús de la distribució de probabilitat uniforme per fer seleccions aleatòries. Per altra banda, el marc Multi-start biased Randomization of classical Heuristics with Adaptive local search proposa l'ús de aleatorització esbiaixada (no uniforme) per al disseny de algoritmes metaheuristics alternatius -i.e., l'ús de distribucions de probabilitat esbiaixades com la geomètrica o la triangular. En algunes situacions, aquesta aleatorització no uniforme ha obtingut una convergència més ràpida a la solució quasi òptima. El marc MIRHA també inclou un pas de cerca local per a millorar les solucions generades durant el procés iteratiu. A més, permet afegir passos de cerca adaptats al problema, com cache (memòria) o splitting (dividir i conquerir), que permeten la generació de solucions competitives (quasi òptimes). Els algoritmes dissenyats amb el marc MIRHA permeten obtenir solucions d'alta qualitat a problemes realistes en temps de computació raonables. A més, tendeixen a utilitzar un nombre reduït de paràmetres, el que els fa simples d'implementar i configurar en la majoria d'aplicacions pràctiques. El marc s'ha aplicat exitosament a diversos problemes d'enrutament i planificació. Un dels principals objectius d'aquesta tesi és desenvolupar nous algoritmes , basats en el marc mencionat, per solucionar problemes d'optimització combinatòria que poden ser d'interès a la industria de les telecomunicacions. / La mayoría de metaheurísticas tienen un componente aleatorio, que normalmente está basada en aleatorización uniforme -ie, el uso de la distribución de probabilidad uniforme para hacer selecciones aleatorias. Por otra parte, el marco Multi-start Biased Randomization of classical heurística with Adaptive local search propone el uso de aleatorización sesgada (no uniforme) para el diseño de algoritmos metaheurísticos alternativos -ie, el uso de distribuciones de probabilidad sesgadas como la geométrica o triangular. En algunas situaciones, esta aleatorización no uniforme ha obtenido una convergencia más rápida en la solución casi óptima. El marco MIRHA también incluye un paso de búsqueda local para mejorar las soluciones generadas durante el proceso iterativo. Además, permite añadir pasos de búsqueda adaptados al problema, como caché (memoria) o splitting (dividir y conquistar), que permiten la generación de soluciones competitivas (casi óptimas). Los algoritmos diseñados con el marco MIRHA permiten obtener soluciones de alta calidad a problemas realistas en tiempo de computación razonables. Además, tienden a utilizar un número reducido de parámetros, lo que los hace simples de implementar y configurar en la mayoría de aplicaciones prácticas. El marco se ha aplicado exitosamente a varios problemas de enrutamiento y planificación. Uno de los principales objetivos de esta tesis es desarrollar nuevos algoritmos, basados ¿¿en el marco mencionado, para solucionar problemas de optimización combinatoria que pueden ser de interés en la industria de las telecomunicaciones. / Most metaheuristics contain a randomness component, which is usually based on uniform randomization -i.e., the use of the Uniform probability distribution to make random choices. However, the Multi-start biased Randomization of classical Heuristics with Adaptive local search framework proposes the use of biased (non-uniform) randomization for the design of alternative metaheuristics -i.e., the use of skewed probability distributions such as the Geometric or Triangular ones. In some scenarios, this non-biased randomization has shown to provide faster convergence to near-optimal solutions. The MIRHA framework also includes a local search step for improving the incumbent solutions generated during the multi-start process. It also allows the addition of tailored local search components, like cache (memory) or splitting (divide-and-conquer) techniques, that allow the generation of competitive (near-optimal) solutions. The algorithms designed using the MIRHA framework allows to obtain "high-quality" solutions to realistic problems in reasonable computing times. Moreover, they tend to use a reduced number of parameters, which makes them simple to implement and configure in most practical applications. This framework has successfully been applied in many routing and scheduling problems. One of the main goals of this thesis is to develop new algorithms, based in the aforementioned framework, for solving some combinatorial optimization problems that can be of interest in the telecommunication industry.

En aquesta tesi s'estudia la dimensió mètrica forta de grafs producte. Els resultats més importants de la tesi se centren en la recerca de relacions entre la dimensió mètrica forta de grafs producte i la dels seus factors, juntament amb altres invariants d'aquests factors. Així, s'han estudiat els següents productes de grafs: producte cartesià, producte directe, producte fort, producte lexicogràfic, producte corona, grafs unió, suma cartesiana, i producte arrel, d'ara endavant "grafs producte". Hem obtingut fórmules tancades per la dimensió mètrica forta de diverses famílies no trivials de grafs producte que inclouen, per exemple, grafs bipartits, grafs vèrtexs transitius, grafs hamiltonians, arbres, cicles, grafs complets, etc, i hem donat fites inferiors i superiors generals, expressades en termes d'invariants dels grafs factors, com ara, l'ordre, el nombre d'independència, el nombre de cobriment de vèrtexs, el nombre d'aparellament, la connectivitat algebraica, el nombre de cliqué, i el nombre de cliqué lliure de bessons. També hem descrit algunes classes de grafs producte, on s'assoleixen aquestes fites. És conegut que el problema de trobar la dimensió mètrica forta d'un graf connex es pot transformar en el problema de trobar el nombre de cobriment de vèrtexs de la seva corresponent graf de resolubilitat forta. En aquesta tesi hem aprofitat aquesta eina i hem trobat diverses relacions entre el graf de resolubilitat forta de grafs producte i els grafs de resolubilitat forta dels seus factors. Per exemple, és notable destacar que el graf de resolubilitat forta del producte cartesià de dos grafs és isomorf al producte directe dels grafs de resolubilitat forta dels seus factors. / En esta tesis se estudia la dimensión métrica fuerte de grafos producto. Los resultados más importantes de la tesis se centran en la búsqueda de relaciones entre la dimensión métrica fuerte de grafos producto y la de sus factores, junto con otros invariantes de estos factores. Así, se han estudiado los siguientes productos de grafos: producto cartesiano, producto directo, producto fuerte, producto lexicográfico, producto corona, grafos unión, suma cartesiana, y producto raíz, de ahora en adelante "grafos producto". Hemos obtenido fórmulas cerradas para la dimensión métrica fuerte de varias familias no triviales de grafos producto que incluyen, por ejemplo, grafos bipartitos, grafos vértices transitivos, grafos hamiltonianos, árboles, ciclos, grafos completos, etc, y hemos dado cotas inferiores y superiores generales, expresándolas en términos de invariantes de los grafos factores, como por ejemplo, el orden, el número de independencia, el número de cubrimiento de vértices, el número de emparejamiento, la conectividad algebraica, el número de cliqué, y el número de cliqué libre de gemelos. También hemos descrito algunas clases de grafos producto, donde se alcanzan estas cotas. Es conocido que el problema de encontrar la dimensión métrica fuerte de un grafo conexo se puede transformar en el problema de encontrar el número de cubrimiento de vértices de su correspondiente grafo de resolubilidad fuerte. En esta tesis hemos aprovechado esta herramienta y hemos encontrado varias relaciones entre el grafo de resolubilidad fuerte de grafos producto y los grafos de resolubilidad fuerte de sus factores. Por ejemplo, es notable destacar que el grafo de resolubilidad fuerte del producto cartesiano de dos grafos es isomorfo al producto directo de los grafos de resolubilidad fuerte de sus factores. / In this thesis we study the strong metric dimension of product graphs. The central results of the thesis are focused on finding relationships between the strong metric dimension of product graphs and that of its factors together with other invariants of these factors. We have studied the following products: Cartesian product graphs, direct product graphs, strong product graphs, lexicographic product graphs, corona product graphs, join graphs, Cartesian sum graphs, and rooted product graphs, from now on ``product graphs''. We have obtained closed formulaes for the strong metric dimension of several nontrivial families of product graphs involving, for instance, bipartite graphs, vertex-transitive graphs, Hamiltonian graphs, trees, cycles, complete graphs, etc., or we have given general lower and upper bounds, and have expressed these in terms of invariants of the factor graphs like, for example, order, independence number, vertex cover number, matching number, algebraic connectivity, clique number, and twin-free clique number. We have also described some classes of product graphs where these bounds are achieved. It is known that the problem of finding the strong metric dimension of a connected graph can be transformed to the problem of finding the vertex cover number of its strong resolving graph. In the thesis we have strongly exploited this tool. We have found several relationships between the strong resolving graph of product graphs and that of its factor graphs. For instance, it is remarkable that the strong resolving graph of the Cartesian product of two graphs is isomorphic to the direct product of the strong resolving graphs of its factors.

This thesis is based on the implementation of a computational system to numerically simulate the interaction between a fluid and an arbitrary number of rigid bodies. This implementation was performed in a distributed memory parallelization context, which makes the process and its description especially challenging. As a consequence, for the sake of descriptive precision and conceptual clarity, a new formal framework using set theory concepts is developed. The fluid is discretized using a non body-conforming mesh and the boundaries of the bodies are embedded in this mesh. The force that the fluid exerts on a body is determined from the residual of the momentum equations. Conversely, the velocity of the body is imposed as a boundary condition in the fluid. In this context, two new approaches are proposed. To account for the fact that fluid nodes can become solid nodes and vice versa due to the rigid body movement, we have adopted the FMALE approach, which is based on the idea of a virtual movement of the fluid mesh at each time step. A new method of interpolation is adopted inside the FMALE implementation in order to improve the results. The physics of the fluid is described by the incompressible Navier-Stokes equations. These equations are stabilized using a variational multiscale finite element method and solved using a fractional step like scheme at the algebraic level. The incompressible Navier-Stokes solver is a parallel solver based on master-worker strategy. The bodies can have arbitrary shapes and their motions are determined by the Newton-Euler equations. The contacts between bodies are solved using impulses to avoid interpenetrations. The time of impact is determined implementing a dynamic collision detection algorithm. As far as the parallel implementation is concerned, the data of all the bodies are shared by all the subdomains. To track the boundary of the bodies in the fluid mesh, computational geometry tools have been used. / Esta tesis se basa en la implementación de un sistema computacional para simular numéricamente la interacción entre un fluido y un número arbitrario de sólidos rígidos. La implementación se llevó a cabo considerando un ambiente de programación paralelo con memoria distribuida, lo que convierte al proceso y a su descripción en un reto importante. Como consecuencia, para una descripción conceptual clara y precisa, un nuevo marco formal se desarrolló utilizando los conceptos de la teoría de conjuntos. El fluido se discretiza utilizando una malla no conforme donde las mallas de contorno de los sólidos rígidos están embebidas. La fuerza que el fluido ejerce sobre un sólido se determina en base al residuo de las ecuaciones de conservación del momento. En cambio, la velocidad del sólido se impone como una condición de contorno en el fluido. En este contexto, en el marco de los métodos de malla de contorno embebidos, se proponen dos nuevas aproximaciones. Para resolver el problema que se plantea cuando un número dado de nodos que pertenecían al fluido se convierten en nodos que pertenecen al sólido y viceversa debido al propio movimiento de los sólidos, hemos adoptado la aproximación conocida como FMALE, la cual se basa en la idea de un movimiento virtual de la malla que discretiza al fluido a cada paso de tiempo. Un nuevo método de interpolación se implementó dentro del método FMALE para mejorar los resultados obtenidos. La física del fluido se describe mediante las ecuaciones de Navier-Stokes. Estas ecuaciones se estabilizaron utilizando el método variacional multiescala de los elementos finitos y se resolvieron utilizando un esquema similar al de los de paso de tiempo fraccionado. En general, los sólidos pueden tener formas arbitrarias y sus movimientos se describen mediante las ecuaciones de Newton-Euler. Los contactos entre sólidos se resuelven usando impulsos para evitar interpenetraciones. El tiempo de contacto se determina implementando un algoritmo de detección de colisiones dinámico. En paralelo, los datos de todos los sólidos se comparten entre todos los subdominios. Sin embargo, para tratar los contornos de los sólidos dentro de la malla no conforme que discretiza el problema, varias herramientas computaciones han sido usadas para reducir el tiempo de ejecución

En aquesta tesi vam introduir la noció de resolubilitat simultània per a famílies de grafs definides sobre un conjunt de vèrtexs en comú. Els principals resultats de la tesi s'han abordat als generadors i bases mètrics simultanis, així com la dimensió mètrica simultània d'aquestes famílies. Addicionalment, hem tractat dues formes de resolubilitat simultània relacionades. Primerament, vam abordar la dimensió d'adjacència simultània, la qual va demostrar la seva utilitat per caracteritzar la dimensió mètrica simultània de famílies compostes per grafs-producte lexicogràfics i corona. En segon lloc, vam estudiar les propietats principals de la dimensió mètrica forta simultània. En tots els casos, el focus va estar a determinar les cotes generals per a aquests paràmetres, les seves relacions amb els paràmetres de resolubilitat estàndard dels grafs individuals i, quan va ser possible, donar valors exactes o cotes ajustades per certes famílies específiques. Des del punt de vista computacional, el problema encara no es pot considerar resolt per al cas general, ja que vam aconseguir verificar que el requisit de simultaneïtat augmenta la complexitat computacional dels càlculs relacionats amb aquests paràmetres, els quals ja s'havia demostrat que eren NP -difícils. En particular, vam caracteritzar famílies compostes per grafs pels quals alguns paràmetres estàndards de resolubilitat es poden calcular eficientment, mentre que calcular els paràmetres simultanis associats és NP-difícil. Per pal•liar aquest problema, vam proposar diversos mètodes per estimar aproximadament aquests paràmetres i vam realitzar una avaluació experimental per estudiar el seu comportament en col•leccions de famílies de grafs generades aleatòriament. / En esta tesis hemos introducido la noción de resolubilidad simultánea para familias de grafos definidas sobre un conjunto de vértices en común. Los principales resultados de la tesis han abordado los generadores y bases métricos simultáneos, así como la dimensión métrica simultánea de dichas familias. Adicionalmente, hemos tratado dos formas de resolubilidad simultánea relacionadas. Primeramente, abordamos la dimensión de adyacencia simultánea, la cual demostró su utilidad para caracterizar la dimensión métrica simultánea de familias compuestas por grafos-producto lexicográficos y corona. En segundo lugar, estudiamos las propiedades principales de la dimensión métrica fuerte simultánea. En todos los casos, el foco estuvo en determinar las cotas generales para estos parámetros, sus relaciones con los parámetros de resolubilidad estándar de los grafos individuales y, cuando fue posible, dar valores exactos o cotas ajustadas para ciertas familias específicas. Desde el punto de vista computacional, los problemas aún no se pueden considerar resueltos para el caso general, ya que logramos verificar que el requisito de simultaneidad aumenta la complejidad computacional de los cálculos relacionados con estos parámetros, los cuales ya se había demostrado que eran NP-difíciles. En particular, caracterizamos familias compuestas por grafos para los cuales algunos parámetros estándares de resolubilidad se pueden calcular eficientemente, mientras que calcular los parámetros simultáneos asociados es NP-difícil. Para paliar este problema, propusimos varios métodos para estimar aproximadamente estos parámetros y realizamos una evaluación experimental para estudiar su comportamiento en colecciones de familias de grafos generadas aleatoriamente. / In this thesis we have introduced the notion of simultaneous resolvability for graph families defined on a common vertex set. The main results of the thesis have dealt with simultaneous metric generators and bases, as well as the simultaneous metric dimension of such families. Additionally, we have covered two related forms of simultaneous resolvability. Firstly, we treated the simultaneous adjacency dimension, which proved useful for characterizing the simultaneous metric dimension of families composed by lexicographic and corona product graphs. Secondly, we studied the main properties of the simultaneous strong metric dimension. In all cases, our focus was on determining the general bounds for these parameters, their relations to the standard resolvability parameters of the individual graphs and, when possible, giving exact values or sharp bounds for a number of specific families. Computationally, these problems are far from solved for the general case, as we were able to verify that the requirement of simultaneity adds on the complexity of the calculations involving these resolvability parameters, which had already been proven to be NP-hard for their standard counterparts. In particular, we characterized families composed by graphs for which some standard resolvability parameters can be efficiently computed, while computing the associated simultaneous parameters is NP-hard. To alleviate this problem, we proposed several methods for approximately estimating these parameters and conducted an experimental evaluation to study their behaviour on randomly generated collections of graph families.

En aquesta tesi s'estudia la dimensió (k,t)-mètrica dels grafs. Particularment s'emfatitza en la dimensió k-mètrica i la dimensió de k-adjacència. Al primer capítol es dedica als conceptes bàsics i les notacions emprades a la tesi. Al segon capítol es determina el més gran enter k, de manera que hi ha una base (k,t) -mètrica d'un graf. Es mostra, a més, que la complexitat temporal de calcular aquest valor de k és cúbica, pel que fa a l'ordre del graf. Al tercer capítol, s'obtenen fórmules tancades i cotes per a la dimensió (k,t) -mètrica d'alguns grafs. Així mateix, es delimita el valor de la dimensió k-mètrica en funció de paràmetres relacionats amb la distància, i es descriuen les classes de grafs en què s’aconsegueixen aquestes cotes com, per exemple, en els arbres. En particular, per a aquests últims, s'estableix una fórmula per calcular la dimensió k-mètrica de qualsevol arbre. També s'estudia la dimensió de k-adjacència de diversos grafs perquè s'ha trobat una forta relació entre la dimensió k-mètrica de productes de grafs i la dimensió de k-adjacència d'un dels seus factors. Aquesta relació permet obtenir nombrosos resultats per al producte lexicogràfic i per al producte corona. A l'últim capítol, es demostra que trobar el més gran enter k, de manera que hi hagi una base (k,t) –mètrica d’un graf, es pot resoldre en temps cúbic pel que fa a l'ordre del graf. Es prova, a més, que el problema de calcular la dimensió és NP-complex a través d'una transformació polinòmica al 3-SAT. Malgrat tot, per la fórmula obtinguda per a la dimensió k-mètrica d’arbres (que es demostra al capítol 3), es proposa un algoritme que es pot resoldre en temps lineal per determinar la dimensió k-mètrica i una base k-mètrica de qualsevol arbre. / En esta tesis se estudia la dimensión (k, t)-métrica de los grafos. Particularmente se enfatiza en la dimensión k-métrica y la dimensión de k-adyacencia. El primer capítulo se dedica a los conceptos básicos y las notaciones empleadas en la tesis. En el segundo capítulo se determina el mayor entero k, de modo que existe una base (k, t)-métrica de un grafo. Se muestra, además, que la complejidad temporal de calcular este valor de k es cúbica, con respecto al orden del grafo. En el tercer capítulo, se obtiene fórmulas cerradas y cotas para la dimensión (k, t)-métrica de algunos grafos. Asimismo, se acota el valor de la dimensión k-métrica en función de parámetros relacionados con la distancia, y se describe las clases de grafos donde estas cotas son alcanzadas, como por ejemplo en los árboles. En particular, para estos últimos, se establece una fórmula para calcular la dimensión k-métrica de cualquier árbol. También se estudia la dimensión de k-adyacencia de varios grafos debido a que se ha encontrado una fuerte relación entre la dimensión k-métrica de productos de grafos y la dimensión de k-adyacencia de uno de sus factores. Esta relación permite obtener numerosos resultados para el producto lexicográfico y el producto corona. En el último capítulo, se demuestra que encontrar el mayor entero k, de modo que exista una base (k, t)-métrica de un grafo, puede resolverse en tiempo cúbico con respecto al orden del grafo. Se prueba además que el problema de calcular la dimensión es NP-complejo a través de una transformación polinómica al 3-SAT. No obstante, por la fórmula obtenida para la dimensión k-métrica de árboles (demostrada en el capítulo 3), se propone un algoritmo que puede ser resuelto en tiempo lineal para determinar la dimensión k-métrica y una base k-métrica de cualquier árbol. / In this thesis we study the (k, t)-metric dimension of graphs. The central results of the thesis are focused on the k-metric dimension and the k-adjacency dimension. The first chapter is devoted to the basic concepts and the notations used in the thesis. In the second chapter we find the largest integer k such that there exists a (k,t)-metric basis of a graph. We also show that the time complexity of computing this value k is cubic with respect to the order of the graph. In the third chapter, we obtain closed formulae and bounds for the (k,t)-metric dimension of some graphs. We also bound the value for the k-metric dimension of graphs in terms of parameters related to the distance and we describe some classes of graphs where these bounds are achieved, such as trees. In particular, we give a formula for computing the k-metric dimension of any tree. We also study the k-adjacency dimension of several graphs due to we have found a strong relationship between the k-metric dimension of product graphs and the k-adjacency dimension of one of its factors. This relationship allows us to obtain several results for the lexicographic product and corona product. In the last chapter, we prove that finding the value k such that there exists a $(k,t)$-metric basis of a graph can be solved in cubic time with respect to the order of the graph. We also show that the problem of computing the k-metric dimension of a graph is NP-Hard through a polynomial transformation from the 3-SAT problem. However, by using a obtained formula for the k-metric dimension of trees (proven in Chapter 3), we propose algorithms, which can be solved in linear time, for determining the k-metric dimension and a k-metric basis of any tree.

The main goal of this thesis is to develop lossless compression schemes for analog and binary sources. All the considered compression schemes have as common feature that the encoder can be represented by a graph, so they can be studied employing tools from modern coding theory. In particular, this thesis is focused on two compression problems: the group testing and the noiseless compressed sensing problems. Although both problems may seem unrelated, in the thesis they are shown to be very close. Furthermore, group testing has the same mathematical formulation as non-linear binary source compression schemes that use the OR operator. In this thesis, the similarities between these problems are exploited. The group testing problem is aimed at identifying the defective subjects of a population with as few tests as possible. Group testing schemes can be divided into two groups: adaptive and non-adaptive group testing schemes. The former schemes generate tests sequentially and exploit the partial decoding results to attempt to reduce the overall number of tests required to label all members of the population, whereas non-adaptive schemes perform all the test in parallel and attempt to label as many subjects as possible. Our contributions to the group testing problem are both theoretical and practical. We propose a novel adaptive scheme aimed to efficiently perform the testing process. Furthermore, we develop tools to predict the performance of both adaptive and non-adaptive schemes when the number of subjects to be tested is large. These tools allow to characterize the performance of adaptive and non-adaptive group testing schemes without simulating them. The goal of the noiseless compressed sensing problem is to retrieve a signal from its lineal projection version in a lower-dimensional space. This can be done only whenever the amount of null components of the original signal is large enough. Compressed sensing deals with the design of sampling schemes and reconstruction algorithms that manage to reconstruct the original signal vector with as few samples as possible. In this thesis we pose the compressed sensing problem within a probabilistic framework, as opposed to the classical compression sensing formulation. Recent results in the state of the art show that this approach is more efficient than the classical one. Our contributions to noiseless compressed sensing are both theoretical and practical. We deduce a necessary and sufficient matrix design condition to guarantee that the reconstruction is lossless. Regarding the design of practical schemes, we propose two novel reconstruction algorithms based on message passing over the sparse representation of the matrix, one of them with very low computational complexity. / El objetivo principal de la tesis es el desarrollo de esquemas de compresión sin pérdidas para fuentes analógicas y binarias. Los esquemas analizados tienen en común la representación del compresor mediante un grafo; esto ha permitido emplear en su estudio las herramientas de codificación modernas. Más concretamente la tesis estudia dos problemas de compresión en particular: el diseño de experimentos de testeo comprimido de poblaciones (de sangre, de presencia de elementos contaminantes, secuenciado de ADN, etcétera) y el muestreo comprimido de señales reales en ausencia de ruido. A pesar de que a primera vista parezcan problemas totalmente diferentes, en la tesis mostramos que están muy relacionados. Adicionalmente, el problema de testeo comprimido de poblaciones tiene una formulación matemática idéntica a los códigos de compresión binarios no lineales basados en puertas OR. En la tesis se explotan las similitudes entre todos estos problemas. Existen dos aproximaciones al testeo de poblaciones: el testeo adaptativo y el no adaptativo. El primero realiza los test de forma secuencial y explota los resultados parciales de estos para intentar reducir el número total de test necesarios, mientras que el segundo hace todos los test en bloque e intenta extraer el máximo de datos posibles de los test. Nuestras contribuciones al problema de testeo comprimido han sido tanto teóricas como prácticas. Hemos propuesto un nuevo esquema adaptativo para realizar eficientemente el proceso de testeo. Además hemos desarrollado herramientas que permiten predecir el comportamiento tanto de los esquemas adaptativos como de los esquemas no adaptativos cuando el número de sujetos a testear es elevado. Estas herramientas permiten anticipar las prestaciones de los esquemas de testeo sin necesidad de simularlos. El objetivo del muestreo comprimido es recuperar una señal a partir de su proyección lineal en un espacio de menor dimensión. Esto sólo es posible si se asume que la señal original tiene muchas componentes que son cero. El problema versa sobre el diseño de matrices y algoritmos de reconstrucción que permitan implementar esquemas de muestreo y reconstrucción con un número mínimo de muestras. A diferencia de la formulación clásica de muestreo comprimido, en esta tesis se ha empleado un modelado probabilístico de la señal. Referencias recientes en la literatura demuestran que este enfoque permite conseguir esquemas de compresión y descompresión más eficientes. Nuestras contribuciones en el campo de muestreo comprimido de fuentes analógicas dispersas han sido también teóricas y prácticas. Por un lado, la deducción de la condición necesaria y suficiente que debe garantizar la matriz de muestreo para garantizar que se puede reconstruir unívocamente la secuencia de fuente. Por otro lado, hemos propuesto dos algoritmos, uno de ellos de baja complejidad computacional, que permiten reconstruir la señal original basados en paso de mensajes entre los nodos de la representación gráfica de la matriz de proyección.

La premi ere partie de cette th ese s'int eresse au groupage de tra c dans les r eseaux de t el ecommunications. La notion de groupage de tra c correspond a l'agr egation de ux de faible d ebit dans des conduits de plus gros d ebit. Cependant, a chaque insertion ou extraction de tra c sur une longueur d'onde il faut placer dans le noeud du r eseau un multiplexeur a insertion/extraction (ADM). De plus il faut un ADM pour chaque longueur d'onde utilis ee dans le noeud, ce qui repr esente un co^ut d' equipements important. Les objectifs du groupage de tra c sont d'une part le partage e cace de la bande passante et d'autre part la r eduction du co^ut des equipements de routage. Nous pr esentons des r esultats d'inapproximabilit e, des algorithmes d'approximation, un nouveau mod ele qui permet au r eseau de pouvoir router n'importe quel graphe de requ^etes de degr e born e, ainsi que des solutions optimales pour deux sc enarios avec tra c all-to-all: l'anneau bidirectionnel et l'anneau unidirectionnel avec un facteur de groupage qui change de mani ere dynamique. La deuxi eme partie de la th ese s'interesse aux probl emes consistant a trouver des sousgraphes avec contraintes sur le degr e. Cette classe de probl emes est plus g en erale que le groupage de tra c, qui est un cas particulier. Il s'agit de trouver des sous-graphes d'un graphe donn e avec contraintes sur le degr e, tout en optimisant un param etre du graphe (tr es souvent, le nombre de sommets ou d'ar^etes). Nous pr esentons des algorithmes d'approximation, des resultats d'inapproximabilit e, des etudes sur la complexit e param etrique, des algorithmes exacts pour les graphes planaires, ainsi qu'une m ethodologie g en erale qui permet de r esoudre e cacement cette classe de probl emes (et de mani ere plus g en erale, la classe de probl emes tels qu'une solution peut ^etre cod e avec une partition d'un sous-ensemble des sommets) pour les graphes plong es dans une surface. Finalement, plurieurs annexes pr esentent des r esultats sur des probl emes connexes.