Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-08-12T15:13:32Z No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5) / Made available in DSpace on 2014-08-12T15:13:32Z (GMT). No. of bitstreams: 2 license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) dissertacao rommel cc.pdf: 1665635 bytes, checksum: 9f894f847272036c011387e2de71507f (MD5) Previous issue date: 2009-03-12 / Given a graph G = (V;E) and a set of vertices D V, a vertice v 2 V is dominated by D if jN[v] \ Dj 1. When jN(v) \ Dj = 1 for all v 2 V, G is efficiently dominable. A generalization of this concept is called efficient multiple domination, which requires all vertices must be dominated by a set D V exactly k times. The aim of this dissertation is to study these topics, describing the theoretical knowledge needed for advanced researches. For this reason, many of the theorems and its proofs are detailed. Furthermore, some results on the efficient multiple domination are presented, including bounds for the size of efficient k-dominating sets, the complement and iterated line graphs of efficiently (r + 1)-dominable r-regular graphs and a N P-completeness proof for the efficient multiple domination problem in arbitrary graphs. It is expected that this work contribute to the development of future researches on the efficient domination and in the resolution of some open problems. / Dado um grafo G = (V;E) e um subconjunto de vértices D V, define-se D como um conjunto dominante de G se todo vértice v 2 V que não estiver incluído no conjunto D for adjacente a pelo menos um vértice de D. Na situação em que, para todo v 2 V, jN[v]\Dj = 1, diz-se que o grafo G é eficientemente dominado. Uma generalização desse conceito consiste na múltipla dominação eficiente, em que é requerido que todo vértice do grafo seja dominado exatamente k vezes. O objetivo deste trabalho é realizar um estudo exploratório sobre esses temas, de modo a reunir o conhecimento teórico requerido para pesquisas avançadas. Para isso, buscou-se a apresentação e o detalhamento das demonstrações dos teoremas estudados. Além disso, foram fornecidos alguns resultados sobre a múltipla dominação eficiente no que se refere aos limites para o tamanho de um conjunto k-dominante eficiente, à relação da k-dominação eficiente entre grafos regulares, seu complemento e seus grafos linha iterados, bem como à caracterização da N P-completude para o problema da múltipla dominação eficiente em grafos arbitrários. Espera-se que esta dissertação forneça subsídios teóricos para estudos futuros voltados à dominação eficiente, bem como à resolução de algumas questões em aberto.

Based on the author's Ph. D. thesis, University of California, Berkeley, 1993. / Includes bibliographical references (p. [73]-78) and index. Also issued online.

We say a graph is locally P if the induced graph on the neighbourhood of every vertex has the property P. Specically, a graph is locally traceable (LT) or locally hamiltonian (LH) if the induced graph on the neighbourhood of every vertex is traceable or hamiltonian, respectively. A locally locally hamiltonian (L2H) graph is a graph in which the graph induced by the neighbourhood of each vertex is an LH graph. This concept is generalized to an arbitrary degree of nesting, to make it possible to work with LkH graphs. This thesis focuses on the global cycle properties of LT, LH and LkH graphs. Methods are developed to construct and combine such graphs to create others with desired properties. It is shown that with the exception of three graphs, LT graphs with maximum degree no greater than 5 are fully cycle extendable (and hence hamiltonian), but the Hamilton cycle problem for LT graphs with maximum degree 6 is NP-complete. Furthermore, the smallest nontraceable LT graph has order 10, and the smallest value of the maximum degree for which LT graphs can be nontraceable is 6. It is also shown that LH graphs with maximum degree 6 are fully cycle extendable, and that there exist nonhamiltonian LH graphs with maximum degree 9 or less for all orders greater than 10. The Hamilton cycle problem is shown to be NP-complete for LH graphs with maximum degree 9. The construction of r-regular nonhamiltonian graphs is demonstrated, and it is shown that the number of vertices in a longest path in an LH graph can contain a vanishing fraction of the vertices of the graph. NP-completeness of the Hamilton cycle problem for LkH graphs for higher values of k is also investigated. / Mathematical Sciences / D. Phil. (Mathematics)

This thesis presents description of Genetic algorithm. The description begins with theory of complexity and following basic theory of genetic algorithm. Next part explains the principle of all three tasks – travelling salesman problem, knapsack problem and evolution of algorithm for five-in-a-row. The main focus was on developing the algorithm for five-in-a-row. The results were tested with other similar algorithms from internet. In case of travelling salesman problem and knapsack problem, the results were compared with gradient optimization methods.

Bibliography: pages 192-195 / The avoidability, or unavoidability of patterns in words over finite alphabets has been studied extensively. The word α over a finite set A is said to be unavoidable for an infinite set B+ of nonempty words over a finite set B if, for all but finitely many elements w of B+, there exists a semigroup morphism φ ∶ A+ → B+ such that φ(α) is a factor of w. In this treatise, we start by presenting a historical background of results that are related to unavoidability. We present and discuss the most important theorems surrounding unavoidability in detail. We present various complexity-related properties of unavoidable words. For words that are unavoidable, we provide a constructive upper bound to the lengths of words that avoid them. In particular, for a pattern α of length n over an alphabet of size r, we give a concrete function N(n, r) such that no word of length N(n, r) over the alphabet of size r avoids α. A natural subsequent question is how many unavoidable words there are. We show that the fraction of words that are unavoidable drops exponentially fast in the length of the word. This allows us to calculate an upper bound on the number of unavoidable patterns for any given finite alphabet. Subsequently, we investigate computational aspects of unavoidable words. In particular, we exhibit concrete algorithms for determining whether a word is unavoidable. We also prove results on the computational complexity of the problem of determining whether a given word is unavoidable. Specifically, the NP-completeness of the aforementioned problem is established. / Decision Sciences / D. Phil. (Operations Research)

This diploma thesis deals with evolutionary algorithms used for travelling salesman problem (TSP). In the first section, there are theoretical foundations of a graph theory and computational complexity theory. Next section contains a description of chosen optimization algorithms. The aim of the diploma thesis is to implement an application that solve TSP using evolutionary algorithms.