The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.

[ES] La planificación de la distribución espacial en plantas industriales (FLP) es una de las decisiones más importantes en el contexto de la dirección de operaciones, y uno de los problemas de mayor discusión en la literatura científica enmarcada en el campo amplio de la ingeniería industrial. Sin embargo, el uso generalizado del enfoque de solución top-down tradicional, que se inicia con el diseño de la distribución del conjunto de los departamentos o celdas de trabajo que conforman el sistema de producción y prosigue con la distribución detallada al interior de éstos, parte de asunciones poco compatibles con la realidad operacional industrial que implican ciertas limitaciones para su adopción en la práctica. Esto, unido al hecho de que los modelos matemáticos empleados en la generación de alternativas de layout utilizan en su mayoría el coste de manejo de materiales como una función monoobjetivo de carácter cuantitativo, desvirtuando la naturaleza multiobjetiva del problema, acentúa un vacío que genera oportunidades de mejora en la toma de decisiones de planificación del layout en la práctica industrial. En este contexto, esta tesis doctoral, respaldada por un estudio minucioso del estado del arte y el análisis de modelos de optimización matemática de referencia, presenta un marco conceptual para la toma de decisiones de planificación del FLP desde una perspectiva multiobjetivo, y un nuevo modelo de optimización multiobjetivo no lineal entero mixto (MOMINLP) para facilitar la toma de decisiones de distribución espacial en plantas industriales metalmecánicas en entornos de demanda dinámicos mediante un enfoque de planificación bottom-up, teniendo en cuenta criterios cuantitativos y cualitativos. El modelo propuesto, denominado bottom-up mDFLP, considera tres funciones objetivo que pretenden: (1) minimizar el coste total de manejo de materiales y el coste total de reorganización, (2) maximizar el rating de proximidad subjetiva entre departamentos, y (3) maximizar el ratio de utilización de área. El modelo bottom-up mDFLP ha sido validado en una empresa del sector metalmecánico, confirmando un mejor desempeño en los valores de las funciones objetivo respecto a los obtenidos en la distribución en planta actual. / [CA] La planificació de la distribució espacial en plantes industrials (FLP) és una de les decisions més importants en el context de la direcció d'operacions, i un dels problemes de major discussió en la literatura científica emmarcada en el camp ampli de l'enginyeria industrial. No obstant això, l'ús generalitzat de l'enfocament de solució top-down tradicional, que s'inicia amb el disseny de la distribució del conjunt dels departaments o cel·les de treball que conformen el sistema de producció i prossegueix amb la distribució detallada a l'interior d'aquests, part d'assumpcions poc compatibles amb la realitat operacional industrial que impliquen unes certes limitacions per a la seua adopció en la pràctica. Això, unit al fet que els models matemàtics emprats en la generació d'alternatives de layout utilitzen en la seua majoria el cost de maneig de materials com una funció monoobjetivo de caràcter quantitatiu, desvirtuant la naturalesa multiobjectiva del problema, accentua un buit que genera oportunitats de millora en la presa de decisions de planificació del layout en la pràctica industrial. En aquest context, aquesta tesi doctoral, recolzada per un estudi minuciós de l'estat de l'art i l'anàlisi de models d'optimització matemàtica de referència, presenta un marc conceptual per a la presa de decisions de planificació del FLP des d'una perspectiva multiobjectiu, i un nou model d'optimització multiobjectiu no lineal enter mixt (MOMINLP) per a facilitar la presa de decisions de distribució espacial en plantes industrials metallmecàniques en entorns de demanda dinàmics mitjançant un enfocament de planificació bottom-up, tenint en compte criteris quantitatius i qualitatius. El model proposat, denominat bottom-up mDFLP, considera tres funcions objectiu que pretenen: (1) minimitzar el cost total de maneig de materials i el cost total de reorganització, (2) maximitzar el rating de proximitat subjectiva entre departaments, i (3) maximitzar el ràtio d'utilització d'àrea. El model bottom-up mDFLP ha sigut validat en una empresa del sector metallmecànic, confirmant un millor acompliment en els valors de les funcions objectiu respecte als obtinguts en la distribució en planta actual. / [EN] Facility layout planning (FLP) is one of the most critical decisions in operations management and one of the most discussed problems in the scientific literature framed in the broad field of industrial engineering. However, the widespread use of the traditional top-down solution approach, which starts with a block layout design phase and continues with the detailed layout within each work cell making up the production system, is based on assumptions that are not very compatible with the industrial operational reality, which implies certain limitations for its adoption in practice. This issue, together with the fact that the mathematical models used in the generation of layout alternatives mostly use the cost of material handling as a single objective function of a quantitative nature, distorting the multi-objective nature of the problem, accentuates a gap that generates opportunities for improvement in the FLP decision making process in industrial practice. In this context, this doctoral thesis, supported by a thorough study of state of the art and the analysis of benchmark mathematical optimisation models, presents a conceptual framework for FLP planning decision making from a multi-objective perspective and also a new multi-objective mixed-integer non-linear optimisation model (MOMINLP) to facilitate FLP decision making for metal-mechanical industrial plants in dynamic demand environments through a bottom-up planning approach, taking into account quantitative and qualitative criteria. The proposed model, called bottom-up mDFLP, considers three objective functions that aim to: (1) minimising the total material handling cost and the total rearrangement cost, (2) maximising the subjective closeness rating between departments, (3) maximising the area utilisation ratio. The bottom-up mDFLP model has been validated in a company from the metal-mechanical sector, confirming a better performance in the values of the objective functions than those obtained in the current plant layout. / Pérez Gosende, PA. (2022). Enfoque multiobjetivo bottom-up para la planificación dinámica de la distribución espacial en plantas industriales [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/185800

Cette étude s’appuie sur l’enseignement de la lecture-compréhension en français pour un public universitaire débutant en FLE au Brésil. Après avoir fait le point sur cette approche didactique et les enjeux de l’enseignement-apprentissage de la lecture en langue étrangère, dans lequel l’acquisition lexicale joue un rôle important, nous rappelons des notions-clés de la lexicologie et de la sémantique lexicale et présentons le cadre des travaux développés en lexicographie pédagogique, où nous situons plus précisément notre travail. En effet, malgré la diffusion de cet enseignement parmi les étudiants en Amérique latine et sa constante réélaboration afin de rendre compte de nouvelles situations d’apprentissage, il présente des lacunes importantes. Ces lacunes se trouvent autour d’un point névralgique pour une grande partie des lecteurs : le déficit lexical. Un déficit qui n’est pas lié qu’à un simple manque de vocabulaire, mais qui passe aussi par un savoir-apprendre les mots. Cette situation est mise à l’épreuve dans cette thèse par deux recherches expérimentales. Une première recherche à caractère plutôt prospectif vise à repérer le rôle du dictionnaire, et particulièrement du dictionnaire bilingue lors de la lecture et l’effet de son usage sur la construction du sens. Une deuxième recherche met en rapport l’emploi de deux outils lexicographiques, un dictionnaire bilingue et un dictionnaire pédagogique destiné à des apprenants de FLE. Ces recherches nous donnent des pistes essentielles pour l’intégration de l’étude lexicale à ce genre d’enseignement et sont complétées par l’analyse des dictionnaires disponibles pour ce public particulier. Ce parcours nous aide à tracer les principes méthodologiques pour l’élaboration d’un dictionnaire pédagogique d’appui à la lecture et à l’acquisition lexicale fondés sur la lexicographie fonctionnelle. / This study is based on the teaching model of reading French as a foreign language by university students who are beginners in this language in Brazil. After presenting the essential topics of this didactic approach and the issues related to the teaching-learning process when reading in a foreign language, in which the lexical acquisition plays a major role, we present the basics of lexicology and lexical semantics, and finally we portray the works developed in pedagogical lexicography, in which we place this study. Regardless of its dissemination among Latin America students and of its continuous reformulation to account for new learning situations, this teaching method contains some gaps. The gaps refer to a critical issue for a large number of readers: the lack of lexical knowledge. This issue relates not only to a lack of vocabulary knowledge, but also to the ability of word learning. In this study, this question has been further studied based on two experimental researches. The first one, using a more prospective approach, aims at identifying the role of the dictionary–especially bilingual dictionaries–in the reading process and the effects of dictionary use in the construction of meaning. The second one compares the use of two lexicographic instruments: a bilingual dictionary and a pedagogical dictionary for learners of French as a foreign language. Both researches yield important information about the integration of a lexical study with this teaching model; additionally, they are complemented by the analysis of the dictionaries available to this target audience. In this way, we can set methodological principles to build a pedagogical dictionary that helps students in reading activities and that supports vocabulary acquisition on the basis of functional lexicography.

Cette étude s’appuie sur l’enseignement de la lecture-compréhension en français pour un public universitaire débutant en FLE au Brésil. Après avoir fait le point sur cette approche didactique et les enjeux de l’enseignement-apprentissage de la lecture en langue étrangère, dans lequel l’acquisition lexicale joue un rôle important, nous rappelons des notions-clés de la lexicologie et de la sémantique lexicale et présentons le cadre des travaux développés en lexicographie pédagogique, où nous situons plus précisément notre travail. En effet, malgré la diffusion de cet enseignement parmi les étudiants en Amérique latine et sa constante réélaboration afin de rendre compte de nouvelles situations d’apprentissage, il présente des lacunes importantes. Ces lacunes se trouvent autour d’un point névralgique pour une grande partie des lecteurs : le déficit lexical. Un déficit qui n’est pas lié qu’à un simple manque de vocabulaire, mais qui passe aussi par un savoir-apprendre les mots. Cette situation est mise à l’épreuve dans cette thèse par deux recherches expérimentales. Une première recherche à caractère plutôt prospectif vise à repérer le rôle du dictionnaire, et particulièrement du dictionnaire bilingue lors de la lecture et l’effet de son usage sur la construction du sens. Une deuxième recherche met en rapport l’emploi de deux outils lexicographiques, un dictionnaire bilingue et un dictionnaire pédagogique destiné à des apprenants de FLE. Ces recherches nous donnent des pistes essentielles pour l’intégration de l’étude lexicale à ce genre d’enseignement et sont complétées par l’analyse des dictionnaires disponibles pour ce public particulier. Ce parcours nous aide à tracer les principes méthodologiques pour l’élaboration d’un dictionnaire pédagogique d’appui à la lecture et à l’acquisition lexicale fondés sur la lexicographie fonctionnelle. / This study is based on the teaching model of reading French as a foreign language by university students who are beginners in this language in Brazil. After presenting the essential topics of this didactic approach and the issues related to the teaching-learning process when reading in a foreign language, in which the lexical acquisition plays a major role, we present the basics of lexicology and lexical semantics, and finally we portray the works developed in pedagogical lexicography, in which we place this study. Regardless of its dissemination among Latin America students and of its continuous reformulation to account for new learning situations, this teaching method contains some gaps. The gaps refer to a critical issue for a large number of readers: the lack of lexical knowledge. This issue relates not only to a lack of vocabulary knowledge, but also to the ability of word learning. In this study, this question has been further studied based on two experimental researches. The first one, using a more prospective approach, aims at identifying the role of the dictionary–especially bilingual dictionaries–in the reading process and the effects of dictionary use in the construction of meaning. The second one compares the use of two lexicographic instruments: a bilingual dictionary and a pedagogical dictionary for learners of French as a foreign language. Both researches yield important information about the integration of a lexical study with this teaching model; additionally, they are complemented by the analysis of the dictionaries available to this target audience. In this way, we can set methodological principles to build a pedagogical dictionary that helps students in reading activities and that supports vocabulary acquisition on the basis of functional lexicography.

Cette étude s’appuie sur l’enseignement de la lecture-compréhension en français pour un public universitaire débutant en FLE au Brésil. Après avoir fait le point sur cette approche didactique et les enjeux de l’enseignement-apprentissage de la lecture en langue étrangère, dans lequel l’acquisition lexicale joue un rôle important, nous rappelons des notions-clés de la lexicologie et de la sémantique lexicale et présentons le cadre des travaux développés en lexicographie pédagogique, où nous situons plus précisément notre travail. En effet, malgré la diffusion de cet enseignement parmi les étudiants en Amérique latine et sa constante réélaboration afin de rendre compte de nouvelles situations d’apprentissage, il présente des lacunes importantes. Ces lacunes se trouvent autour d’un point névralgique pour une grande partie des lecteurs : le déficit lexical. Un déficit qui n’est pas lié qu’à un simple manque de vocabulaire, mais qui passe aussi par un savoir-apprendre les mots. Cette situation est mise à l’épreuve dans cette thèse par deux recherches expérimentales. Une première recherche à caractère plutôt prospectif vise à repérer le rôle du dictionnaire, et particulièrement du dictionnaire bilingue lors de la lecture et l’effet de son usage sur la construction du sens. Une deuxième recherche met en rapport l’emploi de deux outils lexicographiques, un dictionnaire bilingue et un dictionnaire pédagogique destiné à des apprenants de FLE. Ces recherches nous donnent des pistes essentielles pour l’intégration de l’étude lexicale à ce genre d’enseignement et sont complétées par l’analyse des dictionnaires disponibles pour ce public particulier. Ce parcours nous aide à tracer les principes méthodologiques pour l’élaboration d’un dictionnaire pédagogique d’appui à la lecture et à l’acquisition lexicale fondés sur la lexicographie fonctionnelle. / This study is based on the teaching model of reading French as a foreign language by university students who are beginners in this language in Brazil. After presenting the essential topics of this didactic approach and the issues related to the teaching-learning process when reading in a foreign language, in which the lexical acquisition plays a major role, we present the basics of lexicology and lexical semantics, and finally we portray the works developed in pedagogical lexicography, in which we place this study. Regardless of its dissemination among Latin America students and of its continuous reformulation to account for new learning situations, this teaching method contains some gaps. The gaps refer to a critical issue for a large number of readers: the lack of lexical knowledge. This issue relates not only to a lack of vocabulary knowledge, but also to the ability of word learning. In this study, this question has been further studied based on two experimental researches. The first one, using a more prospective approach, aims at identifying the role of the dictionary–especially bilingual dictionaries–in the reading process and the effects of dictionary use in the construction of meaning. The second one compares the use of two lexicographic instruments: a bilingual dictionary and a pedagogical dictionary for learners of French as a foreign language. Both researches yield important information about the integration of a lexical study with this teaching model; additionally, they are complemented by the analysis of the dictionaries available to this target audience. In this way, we can set methodological principles to build a pedagogical dictionary that helps students in reading activities and that supports vocabulary acquisition on the basis of functional lexicography.

Notre thèse relève du domaine de la lexicographie et plus précisément de la lexicographie contemporaine. Notre étude analyse les dictionnaires historiques comme objet de recherche. Quant à notre problématique de recherche, elle porte sur la constitution de la macrostructure et sur l’élaboration de la microstructure des dictionnaires historiques que sont le Dictionnaire Historique de la Langue Française (le RH), le Dictionnaire Historique de la Langue Anglaise (l’OED) et le Dictionnaire Historique de la Langue Arabe (le DHLA). Les deux premiers dictionnaires historiques sont déjà publiés, alors que le dernier est en cours de compilation.Notre étude comporte deux objectifs principaux. Tout d’abord, elle analyse les éléments de divergence et les éléments de convergence entre la macrostructure et la microstructure des deux dictionnaires historiques, que sont le RH et l’OED. Ensuite, elle examine ces éléments et détermine ceux qui sont applicables dans la constitution de la macrostructure et l’élaboration de la microstructure du DHLA. Pour ce faire, nous avons opté pour l’analyse d’un corpus issu principalement des dictionnaires - le RH et l’OED. Nous avons fait appel également à un corpus secondaire constitué à partir des dictionnaires français, anglais et arabe de langue générale.Notre étude a permis de confirmer que les trois dictionnaires historiques adoptent trois approches différentes dans la constitution de leur macrostructure. Le RH adopte une approche étymologique. Quant à l’OED, il utilise une approche lexicale. Enfin, le DHLA a opté pour une approche complexe. En revanche, ces trois approches sont mises en œuvre en appliquant trois critères, à savoir, tout d‘abord un critère diachronique, puis un critère orthographique et enfin un critère étymologique. En outre, notre étude a permis de confirmer également que la mise en ordre des entrées principales impacte directement la mise en ordre des entrées secondaires.Quant à la microstructure, les trois dictionnaires élaborent la définition de leurs entrées en adoptant relativement le même modèle. En dernière instance, il s’agit d’un modèle construit à partir de trois types d’informations : des informations d’ordre morphologique, des informations d’ordre sémantique et enfin des informations contextuelles. / Our thesis is part of the field of lexicography and more precisely of contemporary lexicography. Our study analyses historical dictionaries as a research object. As for the subject of the thesis, it concerns the constitution of the macrostructure and the development of the microstructure for historical dictionaries, which are: the French Historical Dictionary (RH), the English Historical Dictionary (OED) and the Arabic Historical Dictionary (DHLA). The first two are alread published while the third is in progress.Our study has two main goals. First of all it analyses the divergent and convergent elements between macrostructure and microstructure of both RH and OED historical dictionaries. Then it examines these elements and determines those which are applicable in the constitution of macrostructure and the development of DHLA microstructure. To do this, we have chosen the analysis of a corpus mainly from RH and OED dictionaries. We have also appealed to a secondary corpus constituted from general language dictionaries.Our study has affirmed that the three historical dictionaries adopt three different approaches to constitute their macrostructure: etymological for the RH and lexical for the OED, while the DHLA has opted for a complex approach. However these three approaches are implemented by applying three criteria namely, diachronic criterion, orthographical criterion, and etymological criterion. Our study also confirmed that putting main entrances in order directly impacts on the secondary entrances order.As for the microstructure, the three dictionaries elaborate the definition of their entrances by adopting a relatively similar model, built upon three types of information: morphological information, semantic information and contextual information.

Combinatorial objects can be represented by strings, such as 21534 for the permutation (1 2) (3 5 4), or 110100 for the binary tree corresponding to the balanced parentheses (()()). Given a string s = s1 s2 sn, the right-shift operation shift(s, i, j) replaces the substring si si+1..sj by si+1..sj si. In other words, si is right-shifted into position j by applying the permutation (j j−1 .. i) to the indices of s. Right-shifts include prefix-shifts (i = 1) and adjacent-transpositions (j = i+1). A fixed-content language is a set of strings that contain the same multiset of symbols. Given a fixed-content language, a shift Gray code is a list of its strings where consecutive strings differ by a shift. This thesis asks if shift Gray codes exist for a variety of combinatorial objects. This abstract question leads to a number of practical answers. The first prefix-shift Gray code for multiset permutations is discovered, and it provides the first algorithm for generating multiset permutations in O(1)-time while using O(1) additional variables. Applications of these results include more efficient exhaustive solutions to stacker-crane problems, which are natural NP-complete traveling salesman variants. This thesis also produces the fastest algorithm for generating balanced parentheses in an array, and the first minimal-change order for fixed-content necklaces and Lyndon words. These results are consequences of the following theorem: Every bubble language has a right-shift Gray code. Bubble languages are fixed-content languages that are closed under certain adjacent-transpositions. These languages generalize classic combinatorial objects: k-ary trees, ordered trees with fixed branching sequences, unit interval graphs, restricted Schr oder and Motzkin paths, linear-extensions of B-posets, and their unions, intersections, and quotients. Each Gray code is circular and is obtained from a new variation of lexicographic order known as cool-lex order. Gray codes using only shift(s, 1, n) and shift(s, 1, n−1) are also found for multiset permutations. A universal cycle that omits the last (redundant) symbol from each permutation is obtained by recording the first symbol of each permutation in this Gray code. As a special case, these shorthand universal cycles provide a new fixed-density analogue to de Bruijn cycles, and the first universal cycle for the "middle levels" (binary strings of length 2k + 1 with sum k or k + 1).