Dissertations / Theses on the topic 'Generalized graphs'

Thesis (Ph. D.)--West Virginia University, 1998.
Title from document title page. Document formatted into pages; contains v, 87 p. : ill. Includes abstract. Includes bibliographical references (p. 64-72).

This thesis puts forward the conjecture that for n > 3k with k > 2, the generalized Petersen graph, GP(n,k) is Hamilton-laceable if n is even and k is odd, and it is Hamilton-connected otherwise. We take the first step in the proof of this conjecture by proving the case n = 3k + 1 and k greater than or equal to 1. We do this mainly by means of an induction which takes us from GP(3k + 1, k) to GP(3(k + 2) + 1, k + 2). The induction takes the form of mapping a Hamilton path in the smaller graph piecewise to the larger graph an inserting subpaths we call rotors to obtain a Hamilton path in the larger graph.

Le blockmodeling est un ensemble de techniques initialement conçues pour analyser les réseaux sociaux mais dont l’intérêt pratique devient plus grand, comme nous le verrons plus loin dans cette thèse pour les graphes terminologiques. L’undesobjectifsdublockmodelingestderéduireungrandréseaupotentiellement incohérent en une structure compréhensible plus petite qui peut être interprétée plus facilement. Il y a un grand intérêt à capturer la structure de cluster d’un réseau en termes d’équivalences, de blocs et de partitions. Jusqu’à présent, la plupart des méthodes de modélisationparblocsvisentàadapterlastructureduréseauàunseultypedemodèle de structure. La question de recherche est de savoir comment gérer les situations où un analyste a plusieurs types de relations pour un ensemble d’acteurs. Ainsi, nous proposons un modèle d’optimisation, que nous appelons le extended generalized blockmodeling. Le principal objectif de extended generalized blockmodeling est de trouver la taille de la partition et l’ensemble de modèles qui a la meilleure représentation de la structure du réseau. Le extended generalized blockmodeling élargit les possibilités du framework, permettant d’analyser les réseaux sans aucune connaissance préalable à leur sujet. Leextendedgeneralizedblockmodelingappartientàlaclassedesproblèmeshautementcombinatoires,laméthodeexacteneconvientquepourlespetitsréseaux, doncla deuxièmequestionestdesavoircommentrendrecetteapprocheviablepourlesréseaux moyens et grands. Par conséquent, nous proposons la première approche non exacte pour le extended generalized blockmodeling, basée sur l’algorithme VNS comme alternative pour les réseaux de taille moyenne. Même si les résultats trouvés par l’heuristique ne sont peut-êtrepaslameilleuredetouteslessolutionsauproblème,lesexpériencesmontrent qu’elle converge vers un résultat satisfaisant dans un temps qui n’est pas prohibitif. La troisième question, que nous abordons dans cette thèse, est le extended generalized blockmodeling, une approche appropriée dans le domaine de la bibliométrie et du traitement du langage naturel. Pour ce faire, nous analysons le réseau de termes concernant la recherche sur le terrorisme. Pour toutes ces questions, nous démontrons les résultats numériques, basés sur des benchmarks de jeux de données artificiels et réels. Ces résultats permettent d’explorer lesopportunitésd’applicationdelamodélisationdeblocgénéraliséeétendueainsique ses limites
Blockmodeling is a set of techniques initially designed to analyse social networks but whose practical interest becomes larger, as we will see further in this thesis for terminology graphs. One of the goals of blockmodeling is to reduce a large, potentially incoherent network to a smaller comprehensible structure that can be interpreted more readily. There is great interest in capturing the cluster structure of a network in terms of equivalences, blocks and partitions. Up to now, most blockmodeling methods are focused in fitting the network structure to only one type of structure pattern. However, there are a variety of social networking applications in which it is interesting to consider more than one type of pattern simultaneously, so that the structure of the network can take the form of several indicators for underlying relationships. The research question is, how to deal with the situations where an analyst has several relations types of relations for a set of actors. Thus, we propose an optimization model, which we call the extended generalized blockmodeling. The main objective of extended generalized blockmodeling is to find the partition size and the set of patterns that has the best representation of the network structure. The extended generalized blockmodeling expands the possibilities of the framework, making it possible to analyze networks without any prior knowledge about them. The extended generalized block modeling belongs to the class of highly combinatorial problems, the exact method is only suitable for small networks, so the second question is how to make this approach viable for medium and large networks. Therefore, we propose the first non-exact approach to generalized extended block modeling, based on the VNS algorithm as an alternative for medium-sized networks. Even though the results found by the heuristic may not be the best of all the solutions to the problem, the experiments show that it converges to a satisfactory result in a not prohibitively long time. The third question, which we address in this thesis, is the extended generalized blockmodeling a suitable approach in the field of bibliometrics and Natural Language processing. To do so, we analyse the network of terms concerning terrorism research. For all these questions, we demonstrate the numerical results, based on artificial and real datasets benchmarks. These results allow the exploration of the application opportunities of the extended generalized block modeling as well as it’s limitations

The study of factorization in integral domains has a long history. Unique factorization domains, like the integers, have been studied extensively for many years. More recently, mathematicians have turned their attention to generalizations of this such as Dedekind domains or other domains which have weaker factorization properties. Many authors have sought to generalize the notion of factorization in domains. One particular method which has encapsulated many of the generalizations into a single study is that of τ-factorization, studied extensively by A. Frazier and D.D. Anderson.

Another generalization comes in the form of studying factorization in rings with zero-divisors. Factorization gets quite complicated when zero-divisors are present due to the existence of several types of associate relations as well as several choices about what to consider the irreducible elements.

In this thesis, we investigate several methods for extending the theory of τ-factorization into rings with zero-divisors. We investigate several methods including: 1) the approach used by A.G. Agˇargün and D.D. Anderson, S. Chun and S. Valdes-Leon in several papers; 2) the method of U-factorization developed by C.R. Fletcher and extended by M. Axtell, J. Stickles, and N. Baeth and 3) the method of regular factorizations and 4) the method of complete factorizations.

This thesis synthesizes the work done in the theory of generalized factorization and factorization in rings with zero-divisors. Along the way, we encounter several nice applications of the factorization theory. Using τ _z-factorizations, we discover a nice relationship with zero-divisor graphs studied by I. Beck as well as D.D. Anderson, D.F. Anderson, A. Frazier, A. Lauve, and P. Livingston. Using τ-U-factorization, we are able to answer many questions that arise when discussing direct products of rings.

There are several benefits to the regular factorization factorization approach due to the various notions of associate and irreducible coinciding on regular elements greatly simplifying many of the finite factorization property relationships. Complete factorization is a very natural and effective approach taken to studying factorization in rings with zero-divisors. There are several nice results stemming from extending τ-factorization in this way. Lastly, an appendix is provided in which several examples of rings satisfying the various finite factorization properties studied throughout the thesis are given.

This thesis addresses the problem of inference in factor graphs, especially the LDPC codes, almost solved by message-passing algorithms. In particular, the Belief Propagation algorithm (BP) is investigated as a particular message-passing algorithm whose suboptimality is discussed in the case where the factor graph has a loop-like topology. From the equivalence between the BP and the Bethe approximation in statistical physics that is generalized to the region-based approximation, is detailed the Generalized Belief Propagation algorithm (GBP), a message-passing algorithm between clusters of the factor graph. It is experimentally shown to surpass the BP in the cases where the clustering deals with the harmful topological structures that prevents the BP from rightly decoding any LDPC code, namely the trapping sets. We do not only confront the BP and the GBP algorithms according to their performance from the point of view of the channel coding with the error-rate, but also according to their dynamical behaviors for non-trivial error-events for which both algorithms can exhibit chaotic beahviors. By means of classical and original dynamical quantifiers, it is shown that the GBP algorithm can overcome the BP algorithm.

The study and recognition of graph families (or graph properties) is an essential part of combinatorics. Graph colouring is another fundamental concept of graph theory that can be looked at, in large part, as the recognition of a family of graphs that are colourable according to certain rules. In this thesis, we study additive induced-hereditary families, and some generalisations, from a colouring perspective. Our main results are: · Additive induced-hereditary families are uniquely factorisable into irreducible families. · If P and Q are additive induced-hereditary graph families, then (P,Q)-COLOURING is NP-hard, with the exception of GRAPH 2-COLOURING. Moreover, with the same exception, (P,Q)-COLOURING is NP-complete iff P- and Q-RECOGNITION are both in NP. This proves a 1997 conjecture of Kratochvíl and Schiermeyer. We also provide generalisations to somewhat larger families. Other results that we prove include: · a characterisation of the minimal forbidden subgraphs of a hereditary property in terms of its minimal forbidden induced-subgraphs, and vice versa; · extensions of Mihók's construction of uniquely colourable graphs, and Scheinerman's characterisations of compositivity, to disjoint compositive properties; · an induced-hereditary property has at least two factorisations into arbitrary irreducible properties, with an explicitly described set of exceptions; · if G is a generating set for A ο B, where A and B are indiscompositive, then we can extract generating sets for A and B using a greedy algorithm.

Cette dissertation se divise en deux parties, distinctes mais connexes, qui sont le reflet de la cotutelle. Nous étudions et résolvons des problèmes concernant d'une part la combinatoire des mots dans un contexte abélien et d'autre part des problèmes de couverture dans des graphes. Chaque question fait l'objet d'un chapitre. En combinatoire des mots, le premier problème considéré s'intéresse à la régularité des suites au sens défini par Allouche et Shallit. Nous montrons qu'une suite qui satisfait une certaine propriété de symétrie est 2-régulière. Ensuite, nous appliquons ce théorème pour montrer que les fonctions de complexité 2-abélienne du mot de Thue--Morse ainsi que du mot appelé ''period-doubling'' sont 2-régulières. Les calculs et arguments développés dans ces démonstrations s'inscrivent dans un schéma plus général que nous espérons pouvoir utiliser à nouveau pour prouver d'autres résultats de régularité. Le deuxième problème poursuit le développement de la notion de mot de retour abélien introduite par Puzynina et Zamboni. Nous obtenons une caractérisation des mots sturmiens avec un intercepte non nul en termes du cardinal (fini ou non) de l'ensemble des mots de retour abélien par rapport à tous les préfixes. Nous décrivons cet ensemble pour Fibonacci ainsi que pour Thue--Morse (bien que cela ne soit pas un mot sturmien). Nous étudions la relation existante entre la complexité abélienne et le cardinal de cet ensemble. En théorie des graphes, le premier problème considéré traite des codes identifiants dans les graphes. Ces codes ont été introduits par Karpovsky, Chakrabarty et Levitin pour modéliser un problème de détection de défaillance dans des réseaux multiprocesseurs. Le rapport entre la taille optimale d'un code identifiant et la taille optimale du relâchement fractionnaire d'un code identifiant est comprise entre 1 et 2 ln(|V|)+1 où V est l'ensemble des sommets du graphe. Nous nous concentrons sur les graphes sommet-transitifs, car nous pouvons y calculer précisément la solution fractionnaire. Nous exhibons des familles infinies, appelées quadrangles généralisés, de graphes sommet-transitifs pour lesquelles les solutions entière et fractionnaire sont de l'ordre |V|^k avec k dans {1/4, 1/3, 2/5}. Le second problème concerne les (r,a,b)-codes couvrants de la grille infinie déjà étudiés par Axenovich et Puzynina. Nous introduisons la notion de 2-coloriages constants de graphes pondérés et nous les étudions dans le cas de quatre cycles pondérés particuliers. Nous présentons une méthode permettant de lier ces 2-coloriages aux codes couvrants. Enfin, nous déterminons les valeurs exactes des constantes a et b de tout (r,a,b)-code couvrant de la grille infinie avec |a-b|>4. Il s'agit d'une extension d'un théorème d'Axenovich
This dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter. In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence satisfying a certain symmetry property is 2-regular. Then we apply this theorem to show that the 2-abelian complexity functions of the Thue--Morse word and the period-doubling word are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results. The second question concerns the notion of return words up to abelian equivalence, introduced by Puzynina and Zamboni. We obtain a characterization of Sturmian words with non-zero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the Thue-Morse word (which is not Sturmian). We investigate the relationship existing between the abelian complexity and the finiteness of this set. In graph theory, the first problem considered deals with identifying codes in graphs. These codes were introduced by Karpovsky, Chakrabarty and Levitin to model fault-diagnosis in multiprocessor systems. The ratio between the optimal size of an identifying code and the optimal size of a fractional relaxation of an identifying code is between 1 and 2 ln(|V|)+1 where V is the vertex set of the graph. We focus on vertex-transitive graphs, since we can compute the exact fractional solution for them. We exhibit infinite families, called generalized quadrangles, of vertex-transitive graphs with integer and fractional identifying codes of order |V|^k with k in {1/4,1/3,2/5}. The second problem concerns (r,a,b)-covering codes of the infinite grid already studied by Axenovich and Puzynina. We introduce the notion of constant 2-labellings of weighted graphs and study them in four particular weighted cycles. We present a method to link these labellings with covering codes. Finally, we determine the precise values of the constants a and b of any (r,a,b)-covering code of the infinite grid with |a-b|>4. This is an extension of a theorem of Axenovich

La coloration des graphes est un sujet central en théorie des graphes, et divers concepts de coloration ont été étudiés dans la littérature. Cette thèse étudie certains de ces concepts de coloration et les problèmes associés. Il s'agit notamment de la coloration des graphes signés généralisés, du nombre de choix fractionnels forts des graphes, du nombre de coloration généralisé des graphes, de la largeur gémellaire des graphes, de la discordance (combinatoire) des systèmes d'ensembles définissables et des classes de graphes chi_p-bornées. Un graphe signé est une paire (G, sigma), où G est un graphe et sigma: E(G) to {+,-} est une signature. Un graphe signé généralisé est également une paire (G, sigma), où la signature sigma attribue à chaque arête e une permutation sigma(e) dans un ensemble S comme son signe. Dans une coloration d'un graphe signé ou d'un graphe signé généralisé (G, sigma), le signe sigma(e) détermine les paires de couleurs qui doivent être évitées en tant que couleurs des sommets terminaux de e. Une question naturelle motivée par le théorème des quatre couleurs est de savoir pour quels sous-ensembles S de S_4, tout graphe planaire est S-4-colorable. Cette question a maintenant une réponse complète: seul S={id} posséde cette propriété, ce qui signifie que le théorème des quatre couleurs est strict au sens de la coloration généralisée des graphes signés. Ce résulat a été établi par une séquence de six articles, par différents groupes d'auteurs. L'une des contributions de cette thése est le résultat établi dans l'un de ces articles, à savoir que que de nombreux ensembles S n'ont pas la propriété désirée. La thèse considère également des questions similaires pour les graphes planaires sans triangle, ce qui peut être considéré comme une exploration de l'étanchéité du théorème de Grötzsch. Notre résultat montre que pour tout sous-ensemble S de S_3, si S n'est pas conjugué à un sous-ensemble de {id, (12)}, alors il existe un graphe planaire sans triangle qui n'est pas S-3-colorable. Une autre tentative pour renforcer le théorème de Grötzsch est de considérer le nombre de choix fractionnaire fort des graphes planaires sans triangle. Il a été prouvé par Voigt qu'il existe des graphes planaires sans triangle qui ne sont pas 3-choissables. Cette thèse prouve que le supremum du nombre de choix fractionnel fort des graphes planaires sans triangle est au moins 3+1/17. Un sujet important de la théorie structurelle des graphes est l'étude de la complexité structurelle des graphes. Quelques concepts et invariants de graphes sont largement étudiés dans la littérature. Récemment, le concept de largeur gémellaire a été introduit. Dans cette thèse, nous prouvons qu'un graphe G sans sous graphe K_{s,s} et de largeur gémellaire d a ses nombres de coloration forts (faibles) r bornés supérieurement par une fonction exponentielle en r et que nous pouvons construire des graphes réalisant une telle dépendance en r. L'une des deux notions centrales de la théorie structurelle des classes de graphes éparses est celle de classes d'expansion bornée. La discordance combinatoire est un sujet important. Elle mesure les irrégularités inévitables des systèmes d'ensembles et la difficulté intrinsèque de leur approximation. Dans cette thèse, nous donnons une nouvelle caractérisation des classes d'expansion bornée en termes de discordance de système définissables. La notion de chi-boundedness est un sujet central en théorie des graphes chromatiques. Dans cette thèse, les classes chi-bornées sont étudiées ici dans le contexte des colorations stellaires et, plus généralement, des chi_p-colorations. Considéré dans le cadre général de l'édute des classes éparses, il conduit à des extensions naturelles de la notion de classe d'expansion bornée. Nous résolvons ici deux conjectures liées à la limitation du nombre chromatique stellaire (i.e. chi_2). Nous donnons des caractérisations structurelles des classes (fortement et faiblement) chi_p-bornée
Graph coloring is a central topic in graph theory, and various coloring concepts have been studied in the literature. This thesis studies some of the coloring concepts and related problems. These include coloring of generalized signed graphs, strong fractional choice number of graphs, generalized coloring number of graphs, twin-width of graphs, (combinatorial) discrepancy of definable set systems and chi_p-bounded classes of graphs. A signed graph is a pair (G, sigma), where G is a graph and sigma: E(G) to {+,-} is a signature. A generalized signed graph is also a pair (G, sigma), where the signature sigma assigns to each edge e a permutation sigma(e) in a set S as its sign. In a coloring of a signed graph or a generalized signed graph (G, sigma), the sign sigma(e) determines the pairs of colors that need to be avoided as the colors of the end vertices of e. Let S_k be the set of all permutations of [k]. A natural question motivated by the four color theorem is for which subsets S of S_4, every planar graph is S-4-colorable. This question is now completely answered: only S={id} has this property, which means that the four color theorem is tight in the sense of generalized signed graph coloring. This answer is obtained in a sequence of six papers, by different groups of authors. The contribution of this thesis is the results in one of the papers, which shows that many sets S do not have the desired property. The thesis also considers similar questions for triangle-free planar graphs, which can be viewed as exploring the tightness of Grötzsch Theorem. Our result shows that for any subset S of S_3, if S is not conjugate to a subset of {id, (12)}, then there exists a triangle-free planar graph which is not S-3-colorable. Another attempt to strengthen Grötzsch Theorem is to consider multiple list coloring of triangle-free planar graphs. It was proved by Voigt that there are triangle-free planar graphs that are not 3-choosable. This thesis strengthens Voigt's result by considering the strong fractional choice number of graphs and proves that the supremum of the strong fractional choice number of triangle-free planar graphs is at least 3+1/17. One important subject in structural graph theory is to study the structural complexity of graphs or classes of graphs and a few concepts and graph invariants are studied extensively in the literature. These include treewidth of graphs, generalized coloring number, etc. Recently, the concept of twin-width was introduced by Bonnet, Kim, Thomassé and Watrigant. In this thesis, we study the relation between twin-width and generalized coloring number. We prove that a graph $G$ with no K_{s,s}-subgraph and twin-width d has strong(weak) r-coloring numbers bounded by an exponential function of r and that we can construct graphs achieving such a dependency in r. One of the two central notions in structural theory of classes of sparse graphs is the classes with bounded expansion. These classes have strong algorithmic and structural properties and enjoy numerous characterizations and applications. Combinatorial discrepancy is a significant subject in its own right. It measures the inevitable irregularities of set systems and the inherent difficulty to approximate them. In this thesis, we give a new characterization of bounded expansion classes in terms of discrepancy of definable set systems. The notion of chi-boundedness is a central topic in chromatic graph theory. This thesis studies chi-bounded classes in the context of star colorings and, more generally, chi_p-colorings, say chi_s-bounded and (strongly and weakly) chi_p-bounded classes. This fits to a general scheme of sparsity and leads to natural extensions of the notion of bounded expansion class. Here we solve two conjectures related to star coloring ({i.e.} chi_2) boundedness and give structural characterizations of strongly chi_p-bounded classes and weakly chi_p-bounded classes

Made available in DSpace on 2014-12-17T14:54:48Z (GMT). No. of bitstreams: 1 DiogoPFP_Tese.pdf: 4402228 bytes, checksum: 17eacb6b5f1731f405518c976d32f701 (MD5) Previous issue date: 2006-05-19
Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior
The objective of this thesis is proposes a method for a mobile robot to build a hybrid map of an indoor, semi-structured environment. The topological part of this map deals with spatial relationships among rooms and corridors. It is a topology-based map, where the edges of the graph are rooms or corridors, and each link between two distinct edges represents a door. The metric part of the map consists in a set of parameters. These parameters describe a geometric figure which adapts to the free space of the local environment. This figure is calculated by a set of points which sample the boundaries of the local free space. These points are obtained with range sensors and with knowledge about the robot s pose. A method based on generalized Hough transform is applied to this set of points in order to obtain the geomtric figure. The building of the hybrid map is an incremental procedure. It is accomplished while the robot explores the environment. Each room is associated with a metric local map and, consequently, with an edge of the topo-logical map. During the mapping procedure, the robot may use recent metric information of the environment to improve its global or relative pose
Esta tese tem o objetivo de propor uma metodologia para constru??o de um mapa h?brido de um ambiente interno. A parte topol?gica da representa??o trata das rela??es de conectividade existentes entre as salas e corredores, sendo assim um grafo que representa a topologia do ambiente global. A parte m?trica consiste em armazenar um conjunto de par?metros que descreve uma figura geom?trica plana que melhor se ajusta ao espa?o livre local. Esta figura ? calculada atrav?s do conhecimento de pontos, ou amostras, dos limites do espa?o livre. Estes pontos s?o obtidos com sensores de dist?ncia e a informa??o ? complementada com a estimativa da pose do rob?. Uma vez que estes pontos est?o determinados, o rob? ent?o aplica uma ferramenta baseada na transformada generalizada de Hough para obter a figura em quest?o. O processo de constru??o do mapa ? incremental e totalmente realizado enquanto o rob? explora o ambiente. Cada sala ? representada por este mapa local e cada n? do grafo que representa a topologia do ambiente est? associado a este mapa. Durante o mapeamento o rob? pode utilizar as informa??es rec?m-adquiridas do ambiente para obter uma melhor estimativa de sua pose global ou relativa a uma sala ou corredor

This thesis studies different generalizations of Delaunay triangulations, both from a combinatorial and algorithmic point of view. The Delaunay triangulation of a point set S, denoted DT(S), has vertex set S. An edge uv is in DT(S) if it satisfies the empty circle property: there exists a circle with u and v on its boundary that does not enclose points of S. Due to different optimization criteria, many generalizations of the DT(S) have been proposed. Several properties are known for DT(S), yet, few are known for its generalizations. The main question we explore is: to what extent can properties of DT(S) be extended for generalized Delaunay graphs? First, we explore the connectivity of the flip graph of higher order Delaunay triangulations of a point set S in the plane. The order-k flip graph might be disconnected for k = 3, yet, we give upper and lower bounds on the flip distance from one order-k triangulation to another in certain settings. Later, we show that there exists a length-decreasing sequence of plane spanning trees of S that converges to the minimum spanning tree of S with respect to an arbitrary convex distance function. Each pair of consecutive trees in the sequence is contained in a constrained convex shape Delaunay graph. In addition, we give a linear upper bound and specific bounds when the convex shape is a square. With focus still on convex distance functions, we study Hamiltonicity in k-order convex shape Delaunay graphs. Depending on the convex shape, we provide several upper bounds for the minimum k for which the k-order convex shape Delaunay graph is always Hamiltonian. In addition, we provide lower bounds when the convex shape is in a set of certain regular polygons. Finally, we revisit an affine invariant triangulation, which is a special type of convex shape Delaunay triangulation. We show that many properties of the standard Delaunay triangulations carry over to these triangulations. Also, motivated by this affine invariant triangulation, we study different triangulation methods for producing other affine invariant geometric objects.
Esta tesis estudia diferentes generalizaciones de la triangulación de Delaunay, tanto desde un punto de vista combinatorio como algorítmico. La triangulación de Delaunay de un conjunto de puntos S, denotada DT(S), tiene como conjunto de vértices a S. Una arista uv está en DT(S) si satisface la propiedad del círculo vacío: existe un círculo con u y v en su frontera que no contiene ningún punto de S en su interior. Debido a distintos criterios de optimización, se han propuesto varias generalizaciones de la DT (S). Hoy en día, se conocen bastantes propiedades de la DT(S), sin embargo, poco se sabe sobre sus generalizaciones. La pregunta principal que exploramos es: ¿Hasta qué punto las propiedades de la DT(S) se pueden extender para generalizaciones de gráficas de Delaunay? Primero, exploramos la conectividad de la gráfica de flips de las triangulaciones de Delaunay de orden alto de un conjunto de puntos S en el plano. La gráfica de flips de triangulaciones de orden k = 3 podría ser disconexa, sin embargo, nosotros damos una cota superior e inferior para la distancia en flips de una triangulación de orden k a alguna otra cuando S cumple con ciertas características. Luego, probamos que existe una secuencia de árboles generadores sin cruces tal que la suma total de la longitud de las aristas con respecto a una distancia convexa arbitraria es decreciente y converge al árbol generador mínimo con respecto a la distancia correspondiente. Cada par de árboles consecutivos en la secuencia se encuentran en una triangulación de Delaunay con restricciones. Adicionalmente, damos una cota superior lineal para la longitud de la secuencia y cotas específicas cuando el conjunto convexo es un cuadrado. Aún concentrados en distancias convexas, estudiamos hamiltonicidad en las gráficas de Delaunay de distancia convexa de k-orden. Dependiendo en la distancia convexa, exhibimos diversas cotas superiores para el mínimo valor de k que satisface que la gráfica de Delaunay de distancia convexa de orden-k es hamiltoniana. También damos cotas inferiores para k cuando el conjunto convexo pertenece a un conjunto de ciertos polígonos regulares. Finalmente, re-visitamos una triangulación afín invariante, la cual es un caso especial de triangulación de Delaunay de distancia convexa. Probamos que muchas propiedades de la triangulación de Delaunay estándar se preservan en estas triangulaciones. Además, motivados por esta triangulación afín invariante, estudiamos diferentes algoritmos que producen otros objetos geométricos afín invariantes.

In the first part of the thesis, we introduce a family of simplicial complexes called tree complexes, which generalise the well-known Farey graph. We study numerous aspects of tree complexes. Firstly we show for a given dimension n, the tree complex K(n) is simplicially rigid. We then study the geodesics between a pair of given vertices x and y, giving a bound in terms of the distance between the vertices, and showing that there always exist a pair of vertices at a given distance which attains this bound. When n = 2, this bound is the ith Fibonacci number, where i is the distance between the two vertices. We next study the automorphism group of a tree complex, showing that it splits as a semi-direct product. Finally we study the coarse geometry of a tree complex, showing in particular that for n > 2 each tree complex is quasi-isometric to the simplicial tree T [infinity]. In the second part of the thesis, we study the curve complex of the five-holed sphere, C(S0,5), via subsurface projections to the four-holed sphere. We show that geodesically embedded pentagons, hexagons and heptagons are unique, up to the action of the mapping class group. We conjecture firstly that there are no larger geodesically embedded cycles in C(S0,5), and secondly that these methods might be used in a greatly simplified proof of the hyperbolicity of C(S0,5).

Cette thèse porte sur le développement facilité d'applications de cartographie et de transport, plus particulièrement sur la génération de réseaux piétonniers pour des applications telles que la navigation, le calcul d'itinéraires, l'analyse d'accessibilité et l'urbanisme. Afin d'atteindre ce but, nous proposons un modèle de données à deux couches qui cartographie l'espace public dans une hiérarchie d'objets géospatiaux sémantisés. A bas niveau, la géométrie 2D des objets géospatiaux est représentée par une partition planaire, modélisée par une structure topologique d'arrangement 2D. Cette représentation permet des traitements géométriques efficaces et efficients, ainsi qu'une maintenance et une validation aisée au fur et à mesure des éditions lorsque la géométrie ou la topologie d'un objet sont modifiées. A haut niveau, les aspects sémantiques et thématiques des objets géospatiaux sont modélisés et gérés. La hiérarchie entre ces objets est maintenue à travers un graphe dirigé acyclique dans lequel les feuilles correspondent à des primitives géométriques de l'arrangement 2D et les noeuds de plus haut niveau représentent les objets géospatiaux sémantiques plus ou moins aggrégés. Nous avons intégré le modèle de données proposé dans un framework SIG nommé StreetMaker en complément d'un ensemble d'algorithmes génériques et de capacités SIG basiques. Ce framework est alors assez riche pour générer automatiquement des graphes de réseau piétonnier. En effet, dans le cadre d'un projet d'analyse d'accessibilité, le flux de traitement proposé a permis de produire avec succès sur deux sites un graphe de réseau piétonnier à partir de données en entrées variées : des cartes vectorielles existantes, des données vectorielles créées semi-automatiquement et des objets vectoriels extraits d'un nuage de points lidar issu d'une acquisition de cartographie mobile.Alors que la modélisation 2D de la surface du sol est suffisante pour les applications SIG 2D, les applications SIG 3D nécessitent des modèles 3D de l'environnement. La modélisation 3D est un sujet très large mais, dans un premier pas vers cette modélisation 3D, nous nous sommes concentrés sur la modélisation semi-automatique d'objets de type cylindre généralisé (tels que les poteaux, les lampadaires, les troncs d'arbre, etc) à partir d'une seule image. Les méthodes et techniques développées sont présentées et discutées
This thesis addresses easy and effective development of mapping and transportation applications which especially focuses on the generation of pedestrian networks for applications like navigation, itinerary calculation, accessibility analysis and urban planning. In order to achieve this goal, we proposed a two layered data model which encodes the public space into a hierarchy of semantic geospatial objects. At the lower level, the 2D geometry of the geospatial objects are captured using a planar partition which is represented as a topological 2D arrangement. This representation of a planar partition allows efficient and effective geometry processing and easy maintenance and validation throughout the editions when the geometry or topology of an object is modified. At the upper layer, the semantic and thematic aspects of geospatial objects are modelled and managed. The hierarchy between these objects is maintained using a directed acyclic graph (DAG) in which the leaf nodes correspond to the geometric primitives of the 2D arrangement and the higher level nodes represent the aggregated semantic geospatial objects at different levels. We integrated the proposed data model into our GIS framework called StreetMaker together with a set of generic algorithms and basic GIS capabilities. This framework is then rich enough to generate pedestrian network graphs automatically. In fact, within an accessibility analysis project, the full proposed pipeline was successfully used on two sites to produce pedestrian network graphs from various types of input data: existing GIS vector maps, semi-automatically created vector data and vector objects extracted from Mobile Mapping lidar point clouds.While modelling 2D ground surfaces may be sufficient for 2D GIS applications, 3D GIS applications require 3D models of the environment. 3D modelling is a very broad topic but as a first step to such 3D models, we focused on the semi-automatic modelling of objects which can be modelled or approximated by generalized cylinders (such as poles, lampposts, tree trunks, etc.) from single images. The developed methods and techniques are presented and discussed

Les modèles d'appariements aléatoires représentent de nombreux systèmes stochastiques concrets dans lesquels des éléments de différentes classes sont appariés selon des règles de compatibilités spécifiées. Par exemple, on peut citer les systèmes dédiés à l'allocation d'organes, les sites de recherche d'emplois, de logements, etc. De tels modèles sont toujours associés à un triptyque d'éléments : un graphe connexe, dit de compatibilités, dont les sommets représentent les classes des éléments pouvant entrer dans le systèmeet dont chaque arête relie deux classes compatibles, une politique d'appariements permettant de décider, en cas d'incertitude, quels appariements vont s'effectuer à l'intérieur du système, et un taux d'arrivées selon lequel les éléments entrent en son sein. Dans cette thèse, nous considérons des graphes généralisés, c'est-à-dire que l'on autorise l'appariement de deux éléments de la même classe, et nous étendons donc à ce cadre certains résultats déjà connus dans le cas de graphes simples. La stabilité d'un système régi par un modèle d'appariements est une propriété très importante. En effet, elle assure que les admissions au sein du système étudié sont contrôlées de sorte que les éléments ne restent pas bloqués à l'intérieur et que leur nombre n'augmente pas indéfiniment. Il est donc essentiel que le taux d'arrivées des éléments permette au système d'être stable. Dans ce manuscrit, nous caractérisons de manière algébrique cette zone de stabilité pour certains modèles d'appariements (généraux, généraux avec abandons, bipartis, bipartis étendus) ou de files d'attente, dites skill-based. Par ailleurs, nous démontrons que la politique d'appariements dite First Come, First Matched (FCFM) possède la propriété d'être maximale (généralisée), c'est-à-dire que la zone de stabilité du modèle d'appariements général associé à un graphe de compatibilités et à une politique quelconque est toujours incluse dans celle associée à ce même graphe et à FCFM. Notons que cette dernière coïncide alors avec un ensemble de mesures défini par des conditions purement algébriques. Dans ce cas, la question de l'étude des mesures permettant la stabilité des systèmes régis par un modèle d'appariements revient donc à celle, plus élémentaire, de la caractérisation d'un ensemble déterministe. Nous donnons alors un moyen de construction (simple) des mesures appartenant à celui-ci, ce qui peut s'avérer très utile pour calibrer le contrôle d'accès au système. En effet, la vérification algorithmique qu'une mesure quelconque vérifie ces conditions algébriques nécessite un nombre d'opérations polynomial en le nombre de sommets du graphe, et devient donc très coûteuse à mesure que ce cardinal augmente. Nous explicitons également, sous une forme produit, l'expression de la loi stationnaire de l'évolution temporelle du contenu d'un système stable régi par un modèle d'appariements général et sous la politique FCFM, permettant, notamment, de calculer explicitement des caractéristiques à l'équilibre de systèmes concrets et d'estimer leurs performances en temps long. On peut ainsi, par exemple, calculer la taille moyenne à l'équilibre d'une liste d'attente dans le cadre de dons croisés de reins, ou encore, estimer le temps moyen d'attente sur une interface pair-à-pair ou un site de rencontres.Enfin, les taux d'appariements associés à un modèle d'appariements (général ou biparti étendu) stable sont étudiés. Ils sont définis comme étant les fréquences asymptotiques des appariements réalisés et fournissent un critère de performance des systèmes régis par de tels modèles d'appariements, de même que les propriétés de politique-insensibilité et d'équité de ces taux, qui sont également discutées
Stochastic matching models represent many concrete stochastic systems in which elements of different classes are matched according to specified compatibility rules. For example, we can cite systems dedicated to organs allocation, job search sites, housing allocation programs, etc. Such models are typically associated to a triplet of elements: a connected graph, called compatibility graph, whose vertices represent the classes of elements that can enter the system and whose edges connect two compatible classes, amatching policy which decides the matches to be concretely executed, in case of multiple choices, and an arrival rate according to which the elements enter within it. In this thesis, we consider generalized graphs, meaning that we allow the matching of two elements of the same class, and we therefore extend to this framework some results already known in the case of simple graphs.The stability of a system governed by a matching model is a very important property. It ensures that the admissions within the system under study, are regulated, so that the elements do not accumulate in the system in the long run. It is therefore essential that the arrival rate of the elements allows the system to be stable. In this manuscript, we characterize, algebraically, this stability region for some matching models (general, general with reneging, bipartite, extended bipartite) or skill-based queueing systems.Moreover, we demonstrate that the matching policy called First Come, First Matched (FCFM) has the property of being (generalized) maximal, meaning that the stability region of the general matching model associated with a compatibility graph and with any policy is always included in the one associated with this same graph and ruled by FCFM. Note that this latter then coincides with a set of measures defined by purely algebraic conditions. In this case, the study of stability of the matching model at hand boils down to the more elementary question of characterizing of a deterministic set of measures. We then givea (simple) way to construct the measures belonging to the latter set. This turns out to be very useful for admission control, as checking the algebraic conditions requires a number of operations which is polynomial in the number of vertices of the considered compatibility graph, and therefore becomes very expensive as the number of vertices grows large.We also give, in a product form, the expression of the stationary distribution of the number-in-system process of a stable system governed by a general matching model and under the FCFM policy, allowing, in particular, to explicitly calculate characteristics at equilibrium of concrete systems and to estimate their long-time performance. We can thus, for example, calculate the size average at equilibrium of a waiting list in the case of cross-donation of kidneys, or even, estimate the average waiting time on a peer-to-peerinterface or on a dating website.Finally, the matching rates associated with a stable matching model (general or extended bipartite) are studied. They are defined as the asymptotic frequencies of the executed respective matchings, and provide an insightful performance criterion for the corresponding matching systems, as well as the policy-insensitivity and fairness properties of the matching rates, which are also discussed

One main goal of this thesis is to show that for every K it is possible to find K consecutive natural numbers that cannot be written as sums of three nonnegative cubes. Since it is believed that approximately 10% of all natural numbers can be written in this way, this result indicates that the sums of three cubes distribute unevenly on the real line. These sums have been studied for almost a century, in relation with Waring's problem, but the existence of ``arbitrarily long gaps'' between them was not known. We will provide two proofs for this theorem. The first is relatively elementary and is based on the observation that the sums of three cubes have a positive bias towards being cubic residues modulo primes of the form p=1+3k. Thus, our first method to find consecutive non-sums of three cubes consists in searching them among the natural numbers that are non-cubic residues modulo ``many'' primes congruent to 1 modulo 3. Our second proof is more technical: it involves the computation of the Sato-Tate distribution of the underlying cubic Fermat variety {x^3+y^3+z^3=0}, via Jacobi sums of cubic characters and equidistribution theorems for Hecke L-functions of the Eisenstein quadratic number field Q(\sqrt{-3}). The advantage of the second approach is that it provides a nearly optimal quantitative estimate for the size of gaps: if N is large, there are >>\sqrt{log N}/(log log N)^4 consecutive non-sums of three cubes that are less than N. According to probabilistic models, an optimal estimate would be of the order of log N / log log N. In this thesis we also study other gap problems, e.g. between sums of four fourth powers, and we give an application to the arithmetic of cubic and biquadratic theta series. We also provide the following additional contributions to Number Theory and Combinatorics: a derivation of cubic identities from a parameterization of the pseudo-automorphisms of binary quadratic forms; a multiplicity estimate for multiprojective Chow forms, with applications to Transcendental Number Theory; a complete solution of a problem on planar graphs with everywhere positive combinatorial curvature.

Le contrôle des processus de désassemblage fait référence aux méthodes et aux techniques utilisées pour démonter de manière sûre et efficace des composants mécaniques ou des ensembles complexes. Pour ce faire, des approches de commandes des contrôles sont développés pour satisfaire les contraintes imposées à ces systèmes. Plus précisément, dans cette thèse nous nous s'intéressons à trois types de spécifications : les contraintes marquages, les Contraintes de Marquage Généralisées (CMGs), et les Contraintes d'Exclusions Mutuelles (CEMs).Pour cela, nous avons proposé trois méthodes analytiques. La première contribution concerne une nouvelle technique de conception de lois de commande pour les systèmes de désassemblages afin d'assurer la satisfaction des contraintes de marquage dans des Graphes d'Evénements Temporisés (GETs) avec certaines transitions d'entrée incontrôlables. La deuxième technique met l'accent sur la synthèse des contrôleurs tout en assurant des CMGs spécifiées par des inégalités pondérées dans l'algèbre Min-Plus soumis à des GETs. La dernière approche vise à piloter les processus de désassemblages modélisés par des Réseaux de Graphes d'Evénements Temporisés (RGETs) imposés à des CEMs.En alternative, il convient de noter que ces approches se basent sur les structures conceptuelles des Systèmes à Evénements Discrets (SEDs) ainsi que sur l'algèbre Min-Plus. Ces outils offrent la capacité de représenter de façon exacte et méthodique les systèmes de manufacturier. Par conséquent, la problématique se trouve formulée en utilisant des modèles linéaires de contrôle basés sur l'algèbre Min-Plus. En fait, le comportement de ces graphes est décrite en utilisant des équations Min-Plus linéaires, et les contraintes sont exprimées par des inégalités ou des inégalités pondérées dans l'algèbre Min-Plus.Des conditions suffisantes pour l'existence des lois de commande causales sont établies. Ces contrôleurs développés sont des retours d'états qui peuvent être symbolisés par des places de surveillance empêchant le système de toute violation de contrainte. Le graphe est vivant et sans blocage
Disassembly process control involves the methods and techniques used to safely and efficiently disassemble mechanical components or complex assemblies. To do this, control approaches are developed to satisfy the constraints imposed on these systems. More specifically, in this thesis we are interested in three types of specifications: marking constraints, Generalized Marking Constraints (GMCs), and Mutual Exclusion Constraints (MECs).To this aim, we have proposed three analytical methods. The first contribution concerns a new technique for designing control laws for disassembly systems to ensure the satisfaction of marking constraints in Timed Event Graphs (TEGs) with some uncontrollable input transitions. The second technique focuses on controller synthesis while ensuring GMCs specified by weighted inequalities in the Min-Plus algebra subject to GETs. The final method aims to control disassembly processes modelled by Timed Event Graph Networks (NGETs) imposed on MECs.Alternatively, it is worth noting that these approaches are based on the conceptual structures of Discrete Event Systems (DES) and the Min-Plus algebra. These tools offer the ability to represent manufacturing systems accurately and methodically. Consequently, the problem is formulated using linear control models based on Min-Plus algebra. In fact, the behaviour of these graphs is described using linear Min-Plus equations, and constraints are expressed by inequalities or weighted inequalities in the Min-Plus algebra.Sufficient conditions for the existence of causal control laws are established. These developed controllers are state feedbacks that can be represented by monitoring places preventing the system from any constraint violation. The graph is alive and unblocked

Survey propagation (SP) has recently been discovered as an efficient algorithm in solving classes of hard constraint-satisfaction problems (CSP). Powerful as it is, SP is still a heuristic algorithm, and further understanding its algorithmic nature, improving its effectiveness and extending its applicability are highly desirable. Prior to the work in this thesis, Maneva et al. introduced a Markov Random Field (MRF) formalism for k-SAT problems, on which SP may be viewed as a special case of the well-known belief propagation (BP) algorithm. This result had sometimes been interpreted to an understanding that “SP is BP” and allows a rigorous extension of SP to a “weighted” version, or a family of algorithms, for k-SAT problems. SP has also been generalized, in a non-weighted fashion, for solving non-binary CSPs. Such generalization is however presented using statistical physics language and somewhat difficult to access by more general audience. This thesis generalizes SP both in terms of its applicability to non-binary problems and in terms of introducing “weights” and extending SP to a family of algorithms. Under a generic formulation of CSPs, we first present an understanding of non-weighted SP for arbitrary CSPs in terms of “probabilistic token passing” (PTP). We then show that this probabilistic interpretation of non-weighted SP makes it naturally generalizable to a weighted version, which we call weighted PTP. Another main contribution of this thesis is a disproof of the folk belief that “SP is BP”. We show that the fact that SP is a special case of BP for k-SAT problems is rather incidental. For more general CSPs, SP and generalized SP do not reduce from BP. We also established the conditions under which generalized SP may reduce as special cases of BP. To explore the benefit of generalizing SP to a wide family and for arbitrary, particularly non-binary, problems, we devised a simple weighted PTP based algorithm for solving 3-COL problems. Experimental results, compared against an existing non-weighted SP based algorithm, reveal the potential performance gain that generalized SP may bring.

Cette thèse s'inscrit dans le cadre de l'analyse statistique de données en grande dimension. Nous avons en effet aujourd'hui accès à un nombre toujours plus important d'information. L'enjeu majeur repose alors sur notre capacité à explorer de vastes quantités de données et à en inférer notamment les structures de dépendance. L'objet de cette thèse est d'étudier et d'apporter des garanties théoriques à certaines méthodes d'estimation de structures de dépendance de données en grande dimension.La première partie de la thèse est consacrée à l'étude de modèles parcimonieux et aux méthodes de type Lasso. Après avoir présenté les résultats importants sur ce sujet dans le chapitre 1, nous généralisons le cas gaussien à des modèles exponentiels généraux. La contribution majeure à cette partie est présentée dans le chapitre 2 et consiste en l'établissement d'inégalités oracles pour une procédure Group Lasso appliquée aux modèles linéaires généralisés. Ces résultats montrent les bonnes performances de cet estimateur sous certaines conditions sur le modèle et sont illustrés dans le cas du modèle Poissonien. Dans la deuxième partie de la thèse, nous revenons au modèle de régression linéaire, toujours en grande dimension mais l'hypothèse de parcimonie est cette fois remplacée par l'existence d'une structure de faible dimension sous-jacente aux données. Nous nous penchons dans cette partie plus particulièrement sur la méthode PLS qui cherche à trouver une décomposition optimale des prédicteurs étant donné un vecteur réponse. Nous rappelons les fondements de la méthode dans le chapitre 3. La contribution majeure à cette partie consiste en l'établissement pour la PLS d'une expression analytique explicite de la structure de dépendance liant les prédicteurs à la réponse. Les deux chapitres suivants illustrent la puissance de cette formule aux travers de nouveaux résultats théoriques sur la PLS . Dans une troisième et dernière partie, nous nous intéressons à la modélisation de structures au travers de graphes et plus particulièrement à la détection de communautés. Après avoir dressé un état de l'art du sujet, nous portons notre attention sur une méthode en particulier connue sous le nom de spectral clustering et qui permet de partitionner les noeuds d'un graphe en se basant sur une matrice de similarité. Nous proposons dans cette thèse une adaptation de cette méthode basée sur l'utilisation d'une pénalité de type l1. Nous illustrons notre méthode sur des simulations
This thesis falls within the context of high-dimensional data analysis. Nowadays we have access to an increasing amount of information. The major challenge relies on our ability to explore a huge amount of data and to infer their dependency structures.The purpose of this thesis is to study and provide theoretical guarantees to some specific methods that aim at estimating dependency structures for high-dimensional data. The first part of the thesis is devoted to the study of sparse models through Lasso-type methods. In Chapter 1, we present the main results on this topic and then we generalize the Gaussian case to any distribution from the exponential family. The major contribution to this field is presented in Chapter 2 and consists in oracle inequalities for a Group Lasso procedure applied to generalized linear models. These results show that this estimator achieves good performances under some specific conditions on the model. We illustrate this part by considering the case of the Poisson model. The second part concerns linear regression in high dimension but the sparsity assumptions is replaced by a low dimensional structure underlying the data. We focus in particular on the PLS method that attempts to find an optimal decomposition of the predictors given a response. We recall the main idea in Chapter 3. The major contribution to this part consists in a new explicit analytical expression of the dependency structure that links the predictors to the response. The next two chapters illustrate the power of this formula by emphasising new theoretical results for PLS. The third and last part is dedicated to graphs modelling and especially to community detection. After presenting the main trends on this topic, we draw our attention to Spectral Clustering that allows to cluster nodes of a graph with respect to a similarity matrix. In this thesis, we suggest an alternative to this method by considering a $l_1$ penalty. We illustrate this method through simulations

[Formulae and special characters can only be approximated here. Please see the pdf version of the abstract for an accurate reproduction.] This thesis concerns the study of homogeneous factorisations of complete graphs with edge-transitive factors. A factorisation of a complete graph Kn is a partition of its edges into disjoint classes. Each class of edges in a factorisation of Kn corresponds to a spanning subgraph called a factor. If all the factors are isomorphic to one another, then a factorisation of Kn is called an isomorphic factorisation. A homogeneous factorisation of a complete graph is an isomorphic factorisation where there exists a group G which permutes the factors transitively, and a normal subgroup M of G such that each factor is M-vertex-transitive. If M also acts edge-transitively on each factor, then a homogeneous factorisation of Kn is called an edge-transitive homogeneous factorisation. The aim of this thesis is to study edge-transitive homogeneous factorisations of Kn. We achieve a nearly complete explicit classification except for the case where G is an affine 2-homogeneous group of the form ZR p x G0, where G0 is less than or equal to ΓL(1,p to the power of R). In this case, we obtain necessary and sufficient arithmetic conditions on certain parameters for such factorisations to exist, and give a generic construction that specifies the homogeneous factorisation completely, given that the conditions on the parameters hold. Moreover, we give two constructions of infinite families of examples where we specify the parameters explicitly. In the second infinite family, the arc-transitive factors are generalisations of certain arc-transitive, self-complementary graphs constructed by Peisert in 2001.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
The generalized minimum spanning tree problem is present in several situations of the real world, such as in the context of the telecommunications, transports and grouping of data, where a net of necessary clusters to be connected using a node of each cluster. In that work it is presented the project and the implementation of an algorithm of tabu search with path relinking and iterated local search for the generalized minimum spanning tree problem and your variant with at least one vertex by group. In the computational tests 271 instances of TSPLIB were used generated through the grouping methods Center Clustering and Grid Clustering, and more 20 instances for the extension of the problem with at least one vertex by group. The results demonstrate the efficiency of the algorithm proposed in the obtaining of satisfactory solutions for the two problems.
O problema da árvore geradora mínima generalizado está presente em várias situações do mundo real, tais como no contexto das telecomunicações, transportes e agrupamento de dados, nas quais uma rede de grupos precisa ser conectada utilizando um nodo de cada grupo. Nesse trabalho é apresentado o projeto e a implementação de um algoritmo de busca tabu com reconexão de caminhos e busca local iterativa para o problema da árvore geradora mínima generalizado e sua variante com pelo menos um vértice por grupo. Nos testes computacionais foram utilizadas 271 instâncias da TSPLIB geradas através dos métodos de agrupamento Center Clustering e Grid Clustering, e mais 20 instâncias para a extensão do problema com pelo menos um vértice por grupo. Os resultados demonstram a eficiência do algoritmo proposto na obtenção de soluções satisfatórias para os dois problemas.

The concept of super solutions plays a crucial role in using the constraint satisfaction framework to model many AI problems under uncertain, dynamic, or interactive environments. The availability of large-scale, dynamic, uncertain, and networked data sources in a variety of application domains provides a challenge and opportunity for the constraint programming community, and we expect that super solutions will continue to attract a great deal of interest. In the first part of this thesis, we study the probabilistic behaviour of super solutions of random instances of Boolean Satisability (SAT) and Constraint Satisfaction Problems (CSPs). Our analysis focuses on a special type of super solutions, the (1,0)-super solutions. For random k-SAT, we establish the exact threshold of the phase transition of the solution probability for the cases of k = 2 and 3, and we upper and lower bound the threshold of the phase transition for the case of k ≥ 4. For random CSPs, we derive a non-trivial upper bound on the threshold of phase transitions. Graph colouring is one of the most well-studied problems in graph theory. A solution to a graph colouring problem is a colouring of the vertices such that each colour class is a stable set. A relatively new generalization of graph colouring is cograph colouring, where each colour class is a cograph. Cographs are the minimum family of graphs containing a single vertex and are closed under complementation and disjoint union. We define the cogchromatic number of a graph G as the minimum number of colours needed by a cograph colouring of G. Several problems related to cograph colouring are studied in the second part of this thesis, including properties of graphs that have cog-chromatic number 2; computational hardness of deciding and approximating the cog-chromatic number of graphs; and graphs that are critical in terms of cog-chromatic numbers. Several interesting constructions of graphs with extremal properties with respect to cograph colouring are also presented.
Graduate Studies, College of (Okanagan)
Graduate

Discrete representation of a surface, especially the triangle mesh, is ubiquitous in numerical simulation and computer graphics. Compared with isotropic triangle meshes, anisotropic triangle meshes provide more accurate results in numerical simulation by capturing anisotropic features more faithfully. Furthermore, emerging applications in computer graphics and geometric modeling require reliable differential geometry information estimated on these anisotropic meshes. The first part of this thesis proposes a special type of anisotropic meshes, called shape-preserving meshes, provides guaranteed convergence of discrete differential operators on these meshes and devises an algorithm for generating shape-preserving meshes on free-form surfaces based on the mesh optimization framework with centroidal Voronoi tessellation (CVT). To improve the numerical stability in simulation, we discuss how to reduce the number of obtuse triangles in the mesh. The second part of the thesis discusses the non-uniqueness of anisotropic meshes to represent the same anisotropy defined on a domain, shows that of all anisotropic meshes, there exists one instance minimizing the number of obtuse triangles, and proposes a variational approach to suppressing obtuse triangles in anisotropic meshes by introducing a Minkowski metric in the CVT framework. On a complex shape, its topological information is also highly useful to guide the mesh generation. To extract topology properties, the Morse-Smale complex (MSC) is a classical tool and widely used in computer graphics. However, on a manifold with boundary, its MSC is not well defined. The final part of this thesis generalizes the MSC to manifolds with boundaries. Based on this generalized MSC (GMSC), an operator to merge n GMSCs of manifolds partitioning a large manifold is proposed. The merging operator is used in a divide-and-conquer approach on a massive data set, providing the potential to employ the computational power in a parallel manner.
published_or_final_version
Computer Science
Doctoral
Doctor of Philosophy

Given a positive integer vector ${\ve a}=(a_{1},a_{2}\dots,a_k)^t$ with \bea 1< a_{1}<\cdots