Orientadores: Roberto de Alencar Lotufo, Letícia Rittner / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-25T05:00:23Z (GMT). No. of bitstreams: 1 Souza_RobertoMedeirosde_M.pdf: 27462483 bytes, checksum: fd6e6b42169addd0201eeda81c058aea (MD5) Previous issue date: 2014 / Resumo: A Árvore de Componentes é uma estrutura de dados que representa uma imagem através da relação de hierarquia de seus componentes conexos. Ela é uma estrutura adequada para a implementação de filtros conexos e que foi utilizada com sucesso em muitas aplicações. A Árvore Máxima é uma estrutura compacta para a representação da Árvore de Componentes. A principal contribuiçãoo deste trabalho é a proposta do filtro de Simplificação Maximal da Árvore Máxima (MMS) com dois possíveis critérios para efetuar o seu cálculo: um critério de limiarização normalizada (MMS-T) e um critério de Regiões Extremais Maximamente Estáveis (MMS-MSER). Uma metodologia para aplicar o filtro MMS em associação com o filtro de Extinção, que é formalmente definido nesse trabalho, é apresentada. É mostrado que após a aplicação da metodologia de simplificação, a qual escolhe o número de máximos relevantes a serem mantidos na imagem, o número de nós da Árvore Máxima simplificada é no máximo duas vezes o número de máximos mantidos. Para definir o filtro MMS, novos conceitos, como nó composto e sub-ramo são apresentados. Esses conceitos são importantes para definir muitos algoritmos da Árvore Máxima, e eles possuem interpretações interessantes em termos de processamento de imagem. Possíveis aplicações da metodologia proposta, tais como localização de texto, simplificação/segmentação de imagens e reconhecimento de objetos são ilustrados para mostrar o potencial da metodologia. Também, estudos explortatórios de detecção de regiões salientes em imagens e análise da robustez da topologia da Árvore Máxima são apresentados / Abstract: The Component Tree is a data structure that represents an image through the hierarchical relationship of its connected components. It is an adequate structure to implement connected filters, and it has been successfully used in many applications. The Max-Tree is a compact structure for the Component Tree representation. The main contribution of this work is the proposal of the Maximal Max-Tree Simplification (MMS) filter with two possible criteria to compute the filter: a normalized threshold criterion (MMS-T) and a Maximally Stable Extremal Regions (MSER) criterion (MMS-MSER). A methodology to apply the MMS filter in association to the Extinction filter, which is formally defined in this work, is presented. It is shown that after applying our simplification methodology, which sets the number of relevant maxima in the image to be kept, the number of nodes in the simplified Max-Tree is at most twice this number. In order to define the MMS filter, new concepts, such as composite node and sub-branches are introduced. These concepts are important to define many Max-Tree algorithms, and they have interesting interpretations in terms of image processing. Possible applications of the methodology proposed, such as text location, object recognition, and image simplification/segmentation are illustrated to demonstrate the potential of this methodology. Also, exploratory studies, such as detection of distinguished regions in the image, and analysis of the robustness of the Max-tree topology are presented / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

Orientador: Dessislava Hristova Kochloukova / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T09:11:38Z (GMT). No. of bitstreams: 1 Araujo_PaulaMacedoLinsde_M.pdf: 989128 bytes, checksum: 16ef5d7a0a914714bc4163e7549b1c3a (MD5) Previous issue date: 2014 / Resumo: Estudamos um resultado que se encontra no artigo "Finitely Presented Wreath Products And Double Coset Decompositions" de Y. de Cornulier que afirma que o produto entrelaçado entre os grupos W e G, com respeito a um G-conjunto X, é finitamente apresentável se, e somente se, as seguintes condições são satisfeitas: i. W e G são finitamente apresentáveis; ii. G age sobre X com estabilizadores finitamente gerados; iii. G age diagonalmente sobre X x X com finitas órbitas / Abstract: We study a result in the paper "Finitely Presented Wreath Products And Double Coset Decompositions" by Y. de Cornulier, which asserts that the wreath between the groups W and G with respect to a G-set X is finitely presented if and only if the following conditions hold: i. W and G are finitely presented; ii. G acts on X with finitely generated stabilizers; iii. G acts diagonally on X x X with finitely many orbits / Mestrado / Matematica / Mestra em Matemática

Orientadores: Célia Picinin de Mello, Christiane Neme Campos / Texto em português e inglês / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T12:30:28Z (GMT). No. of bitstreams: 1 Luiz_AtilioGomes_M.pdf: 1439406 bytes, checksum: e2dc07f910b1876087a8f61428919e30 (MD5) Previous issue date: 2014 / Resumo: O problema da coloração total semiforte foi introduzido por Zhang et al. por volta de 2005. Este problema consiste em associar cores às arestas e aos vértices de um grafo G=(V(G),E(G)), utilizando o menor número de cores possível, de forma que: (i) quaisquer dois vértices ou duas arestas adjacentes possuam cores distintas; (ii) cada vértice tenha cor diferente das cores das arestas que nele incidem; e, além disso, (iii) para quaisquer dois vértices adjacentes u,v pertencentes a V(G), o conjunto das cores que colorem u e suas arestas incidentes é distinto do conjunto das cores que colorem v e suas arestas incidentes. Denominamos esse menor número de cores para o qual um grafo admite uma coloração total semiforte como número cromático total semiforte. Zhang et al. também determinaram o número cromático total semiforte de algumas famílias clássicas de grafos e observaram que todas elas possuem uma coloração total semiforte com no máximo Delta(G)+3 cores. Com base nesta observação, eles conjeturaram que Delta(G)+3 cores seriam suficientes para construir uma coloração total semiforte para qualquer grafo simples G. Essa conjetura é denominada Conjetura da Coloração Total Semiforte e permanece aberta para grafos arbitrários, tendo sido verificada apenas para algumas famílias de grafos. Nesta dissertação, apresentamos uma resenha dos principais resultados existentes envolvendo a coloração total semiforte. Além disso, determinamos o número cromático total semiforte para as seguintes famílias: os grafos simples com Delta(G)=3 e sem vértices adjacentes de grau máximo; os snarks-flor; os snarks de Goldberg; os snarks de Blanusa generalizados; os snarks de Loupekine LP1; e os grafos equipartidos completos de ordem par. Verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a Delta(G)+2. Investigamos também a coloração total semiforte dos grafos tripartidos e dos grafos equipartidos completos de ordem ímpar e verificamos que os grafos destas famílias possuem número cromático total semiforte menor ou igual a Delta(G)+3. Os resultados obtidos confirmam a validade da Conjetura da Coloração Total Semiforte para todas as famílias consideradas nesta dissertação / Abstract: The adjacent-vertex-distinguishing-total-colouring (AVD-total-colouring) problem was introduced and studied by Zhang et al. around 2005. This problem consists in associating colours to the vertices and edges of a graph G=(V(G),E(G)) using the least number of colours, such that: (i) any two adjacent vertices or adjacent edges receive distinct colours; (ii) each vertex receive a colour different from the colours of its incident edges; and (iii) for any two adjacent vertices u,v of G, the set of colours that color u and its incident edges is distinct from the set of colours that color v and its incident edges. The smallest number of colours for which a graph G admits an AVD-total-colouring is named its AVD-total chromatic number. Zhang et al. determined the AVD-total chromatic number for some classical families of graphs and noted that all of them admit an AVD-total-colouring with no more than Delta(G)+3 colours. Based on this observation, the authors conjectured that Delta(G)+3 colours would be sufficient to construct an AVD-total-colouring for any simple graph G. This conjecture is called the AVD-Total-Colouring Conjecture and remains open for arbitrary graphs, having been verified for a few families of graphs. In this dissertation, we present an overview of the main existing results related to the AVD-total-colouring of graphs. Furthermore, we determine the AVD-total-chromatic number for the following families of graphs: simple graphs with Delta(G)=3 and without adjacent vertices of maximum degree; flower-snarks; Goldberg snarks; generalized Blanusa snarks; Loupekine snarks; and complete equipartite graphs of even order. We verify that the graphs of these families have AVD-total-chromatic number at most Delta(G)+2. Additionally, we verify that the AVD-Total-Colouring Conjecture is true for tripartite graphs and complete equipartite graphs of odd order. These results confirm the validity of the AVD-Total-Colouring Conjecture for all the families considered in this dissertation / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T17:05:58Z (GMT). No. of bitstreams: 1 Freitas_LucasIsmailyBezerra_M.pdf: 2067916 bytes, checksum: 77f11deab9d862fe9a10de2df94b447c (MD5) Previous issue date: 2014 / Resumo: Neste trabalho estudamos a conjectura de Tuza, que relaciona cobertura mínima de triângulos por arestas com empacotamento máximo de triângulos aresta-disjuntos em grafos. Em 1981, Tuza conjecturou que para todo grafo, o número máximo de triângulos aresta-disjuntos é no máximo duas vezes o tamanho de uma cobertura mínima de triângulos por arestas. O caso geral da conjectura continua aberta. Contudo, diversas tentativas de prová-la surgiram na literatura, obtendo resultados para várias classes de grafos. Nesta dissertação, nós apresentamos os principais resultados obtidos da conjectura de Tuza. Atualmente, existem várias versões da conjectura. Contudo, ressaltamos que nosso foco está na conjectura aplicada a grafos simples. Apresentamos também uma conjectura que se verificada, implica na veracidade da conjectura de Tuza. Demonstramos ainda que se G é um contra-exemplo mínimo para a conjectura de Tuza, então G é 4-conexo. Deduzimos desse resultado que a conjectura de Tuza é válida para grafos sem minor do K_5 / Abstract: In this thesis we study the conjecture of Tuza, which relates covering of triangles (by edges) with packing of edge-disjoint triangles in graphs. In 1981, Tuza conjectured that for any graph, the maximum number of edge-disjoint triangles is at most twice the size of a minimum cover of triangles by edges. The general case of the conjecture remains open. However, several attempts to prove it appeared in the literature, which contain results for several classes of graphs. In this thesis, we present the main known results for the conjecture of Tuza. Currently, there are several versions of Tuza's conjecture. Nevertheless, we emphasize that our focus is on conjecture applied to simple graphs. We also present a conjecture that, if verified, implies the validity of the conjecture of Tuza. We also show that if G is a mininum counterexample to the conjecture of Tuza, then G is 4-connected. We can deduce from this result that the conjecture of Tuza is valid for graphs with no K_5 minor / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Célia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-19T10:47:23Z (GMT). No. of bitstreams: 1 Pedrotti_Vagner_D.pdf: 2015411 bytes, checksum: 4a6917f5811bde65dedbf0f7ab2577c5 (MD5) Previous issue date: 2011 / Resumo: Nesta tese de doutoramento sáo considerados três problemas em grafos, para os quais sáo obtidos resultados quando a entrada é restrita a algumas classes. Todos os problemas sáo problemas de otimização combinatória sobre grafos simples e apresentam diferentes classificações de complexidade. Em dois casos, o estudo focou classes de grafos com "poucos iYs" e ° uso da decomposição modular. No último caso, considerou-se uma subclasse dos grafos de intervalos e a aplicação de uma técnica conhecida como pullback. O primeiro problema estudado é o Problema dos Separadores Minimais, para o qual são conhecidos algoritmos polinomiais em toda classe de grafos que possuir um número polinomial de separadores minimais. Serão dados, como contribuição deste trabalho, um algoritmo linear para listar os separadores minimais de grafos P4-carregados estendidos e limitantes justos no número e tamanho dos separadores minimais destes grafos, bem como de algumas de suas subclasses, P4-carregada, P4-arrumada e P4-íeve. Estes resultados estendem um algoritmo anterior para grafos P4-esparsos, ao mesmo tempo que incluem estas classes de grafos entre as que possuem um número de separadores minimais limitado por um função linear no número de vértices do grafo. Em seguida, será tratado o Problema de Empacotamento de Cliques, uma extensão do problema de emparelhamento máximo. Para a maioria das classes de grafos mais importantes, o problema é NP-Difícil. A contribuição apresentada resolve este problema em tempo polinomial (para qualquer tamanho fixo de clique) em grafos P4-arrumados, através de uma técnica similar a utilizada para os cografos. Infelizmente, para as superclasses mais estudadas da classe P4-arrumada, este problema é NP-Difícil, o que é um indício de que a técnica utilizada foi totalmente aproveitada em relação ás classes com poucos _P4's. Por fim, será estudado o Problema da Coloração Total Forte, uma variação do problema clássico da coloração total, que foi introduzido há pouco tempo e ainda tem sua complexidade computacional desconhecida. Como esperado, existem algoritmos polinomiais apenas para classes bastante simples de grafos. Além da complexidade, outro importante ponto em aberto para o problema é a conjectura de que o número de cores necessárias na solução do problema para um grafo G seria limitado por A(G) + 3. A técnica do pullback, já utilizada para os Problemas de Coloração de Arestas e Coloração Total em grafos dualmente cordais será estendida, resultando em um algoritmo linear para grafos indiferença (também conhecido como grafos de intervalos próprios). Este algoritmo produz uma solução que valida a conjectura nesta classe de grafos. Estas contribuições confirmam a importância da decomposição modular em algoritmos para classes de grafos com "poucos iYs" e ampliam o uso da técnica do pullback para variações dos problemas clássicos de coloração / Abstract: In this doctoral thesis, three problems on graphs are considered and results are given for them when the input is resctricted to some graph classes. All the problems are combinatorial optimization problems on simple graphs and have distinct classihcations of complexity. In two of them, the research focused on graph classes known as graphs with "few iVs" and on the use of modular decomposition on such graphs. In the last problem, a subclass of interval graphs was studied with respect to the application of the technique known as pullback. The first problem studied is the Minimal Separator Problem. For this problem, there exists polynomial time algorithms for every class of graphs which has a polynomial number of minimal separators. A linear-time algorithm, that lists all minimal separators of extended iVladen graphs, is presented. Moreover, tight bounds on the number and on the total size of minimal separators are given for extended iVladen graphs and for some of their subclasses: the iVladen, iVtidy, and iVlite graphs. This result extends a previous algorithm for iVspai'se graphs and gives, for the above classes, better bounds on the number of minimal separators that were already known to be polynomial. Then, the Clique Packing Problem is analyzed. The problem is an extension of the classical Maximum Matching Problem and is NP-Hard for almost all graph classes. The contribution presented solves the problem in polynomial time (for any fixed clique size) in iVtidy graphs through a technique similar to that used for cographs. However, the most well-known superclasses of iVtidy graphs contains split graphs, for which this problem is NP-Hard. This is an evidence that the technique was fully explored with respect of graph classes with few iVs. At last, the Strong Total Coloring Problem is considered. It is a recently introduced variation of the classical Total Coloring Problem and its complexity is still unknown. As expected, there are quite few graph classes for which the problem has a polynomial time algorithm. Besides its complexity, another important open question for this problem is a conjecture which states that A(G) + 3 colors are sufficient for coloring any graph G. A known technique, called pullback, used for edge and total coloring of dually chordal graphs is extended to derive a linear time algorithm for indifference graphs (also known as proper interval graphs). This algorithm produces solutions that validate the conjecture for this graph class. These contributions assert the importance of modular decomposition in algorithms for graph classes with "few P4's" and broaden the pullback technique to variations of classical coloring problems / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Orientador: Célia Picinin de Mello / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T03:13:25Z (GMT). No. of bitstreams: 1 Almeida_SheilaMoraisde_D.pdf: 958566 bytes, checksum: ac97bf74cca2e690531df0f6d05c8a00 (MD5) Previous issue date: 2012 / Resumo: Por apresentar basicamente fórmulas, o resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: Not informed / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

One method to find the node search number of a graph is to prove identical upper and lower bounds. In four types of grid-like graphs. (h. w)-grids. cylinders. orb webs. and walls, upper bounds are easy to see. However. for tori, the upper bounds are less obvious. requiring two different search strategies. In all cases the lower bounds are not obvious and previously unproven. For these five classes of graphs we develop several techniques for proving lower bounds by taking advantage of the fact that re-contamination does help. We observe that in the five classes of graphs we examine, the node search number can be expressed as a function of the height and width of the graph.

Ph.D. / The induced path number p(G) of a graph G is defined as the minimum number of subsets into which the vertex set V(G) of G can be partitioned such that each subset induces a path. In this thesis we determine the induced path number of a complete £-partite graph. We investigate the induced path number of products of complete graphs, of the complement of such products and of products of cycles. For a graph G, the linear vertex arboricity lva(G) is defined as the minimum number of subsets into which the vertex set of C can be partitioned so that each subset induces a linear forest. Since each path is a linear forest, Iva(G) p(G) for each graph C. A graph G is said to be uniquely rn-li near- forest- partition able if lva(C) = in and there is only one partition of V(G) into m subsets so that each subset induces a linear forest. Furthermore, a graph C is defined to be nz- Iva- saturated if Iva(G) < in and lva(C + e) > iii for each e E We construct graphs that are uniquely n2-linear-forest-partitionable and in-lva-saturated. We characterize those graphs that are uniquely m-linear-forest-partitionable and rn-lvasaturated. We also characterize the orders of uniquely in- path- partitionable disconnected, connected and rn-p-saturated graphs. We look at the influence of the addition or deletion of a vertex or an edge on the path partition number. If C is a graph such that p(G) = k and p(G - v) = k - 1 for every v E V(G), then we say that C is k-minus-critical. We prove that if C is a connected graph consisting of cyclic blocks Bi with p(B1 ) = b, for i = 1,2, ... ,n where ii > 2 and k bi - n+ 1, then C is k- minus- critical if and only if each of the blocks B1 is a bj- minus- critical graph.

Recently dominant sets, a generalization of the notion of the maximal clique to edge-weighted graphs, have proven to be an effective tool for unsupervised learning and have found applications in different domains. Although, they were initially established using optimization and graph theory concepts, recent work has shown fascinating connections with evolutionary game theory, that leads to the clustering game framework. However, considering size of today's data sets, existing methods need to be modified in order to handle massive data. Hence, in this research work, first we address the limitations of the clustering game framework for large data sets theoretically. We propose a new important question for the clustering community ``How can a cluster of a subset of a dataset be a cluster of the entire dataset?''. We show that, this problem is a coNP-hard problem in a clustering game framework. Thus, we modify the definition of a cluster from a stable concept to a non-stable but optimal one (Nash equilibrium). By experiments we show that this relaxation does not change the qualities of the clusters practically. Following this alteration and the fact that equilibriums are generally compact subsets of vertices, we design an effective strategy to find equilibriums representing well distributed clusters. After finding such equilibriums, a linear game theoretic relation is proposed to assign vertices to the clusters and partition the graph. However, the method inherits a space complexity issue, that is the similarities between every pair of objects are required which proves practically intractable for large data sets. To overcome this limitation, after establishing necessary theoretical tools for a special type of graphs that we call vertex-repeated graphs, we propose the scalable clustering game framework. This approach divides a data set into disjoint tractable size chunks. Then, the exact clusters of the entire data are approximated by the clusters of the chunks. In fact, the exact equilibriums of the entire graph is approximated by the equilibriums of the subsets of the graph. We show theorems that enable significantly improved time complexity for the model. The applications include, but are not limited to, the maximum weight clique problem, large data clustering and image segmentation. Experiments have been done on random graphs and the DIMACS benchmark for the maximum weight clique problem and on magnetic resonance images (MRI) of the human brain consisting of about 4 million examples for large data clustering. Also, on the Berkeley Segmentation Dataset, the proposed method achieves results comparable to the state of the art, providing a parallel framework for image segmentation and without any training phase. The results show the effectiveness and efficiency of our approach. In another part of this research work, we generalize the clustering game method to cluster uncertain data where the similarities between the data points are not exactly known, that leads to the uncertain clustering game framework. Here, contrary to the ensemble clustering approaches, where the results of different similarity matrices are combined, we focus on the average utilities of an uncertain game. We show that the game theoretical solutions provide stable clusters even in the presence of severe uncertainties. In addition, based on this framework, we propose a novel concept in uncertain data clustering so that every subset of objects can have a ''cluster degree''. Extensive experiments on real world data sets, as well as on the Berkeley image segmentation dataset, confirm the performance of the proposed method. And finally, instead of dividing a graph into chunks to make the clustering scalable, we study the effect of the spectral sparsification method based on sampling by effective resistance on the clustering outputs. Through experimental and theoretical observations, we show that the clustering results obtained from sparsified graphs are very similar to the results of the original non-sparsified graphs. The rand index is always at about 0.9 to 0.99 in our experiments even when lots of sparsification is done.

This dissertation is in two parts, each of three chapters. In Part 1, I shall prove some results concerning variants of the 'secretary problem'. In Part 2, I shall bound several generalizations of the acyclic chromatic number of a graph as functions of its maximum degree. I shall begin Chapter 1 by describing the classical secretary problem, in which the aim is to select the best candidate for the post of a secretary, and its solution. I shall then summarize some of its many generalizations that have been studied up to now, provide some basic theory, and briefly outline the results that I shall prove. In Chapter 2, I shall suppose that the candidates come as ‘m’ pairs of equally qualified identical twins. I shall describe an optimal strategy, a formula for its probability of success and the asymptotic behaviour of this strategy and its probability of success as m → ∞. I shall also find an optimal strategy and its probability of success for the analagous version with ‘c’-tuplets. I shall move away from known posets in Chapter 3, assuming instead that the candidates come from a poset about which the only information known is its size and number of maximal elements. I shall show that, given this information, there is an algorithm that is successful with probability at least ¹/e . For posets with ‘k ≥ 2’ maximal elements, I shall prove that if their width is also ‘k’ then this can be improved to ‘k-1√1/k’ and show that no better bound of this type is possible. In Chapter 4, I shall describe the history of acyclic colourings, in which a graph must be properly coloured with no two-coloured cycle, and state some results known about them and their variants. In particular, I shall highlight a result of Alon, McDiarmid and Reed, which bounds the acyclic chromatic number of a graph by a function of its maximum degree. My results in the next two chapters are of this form. I shall consider two natural generalizations in Chapter 5. In the first, only cycles of length at least ’l’ must receive at least three colours. In the second, every cycle must receive at least ‘c’ colours, except those of length less than ‘c’, which must be multicoloured. My results in Chapter 6 generalize the concept of a cycle; it is now subgraphs with minimum degree ‘r’ that must receive at least three colours, rather than subgraphs with minimum degree two (which contain cycles). I shall also consider a natural version of this problem for hypergraphs.