Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The present dissertation aims to introduce students to high school useful math concepts connectivity problems using graph theory. After the explanation of basic concepts, we introduce the notion of connectedness, Mengers theorem and we present the theorem of Festinger, which is a useful tool for path counts. We also present an application of these concepts in the analysis of electrical sub-distribution network in the state of Sergipe. Finally we conclude this work by suggesting some didactic sequences for high school students addressing the Euler's theorem for graphs, the themes of connectedness, connectivity, Menger's theorem and the theorem Festinger. / A presente disserta c~ao tem como objetivo apresentar aos alunos do ensino m edio conceitos matem aticos uteis na an alise e resolu c~ao de problemas de conectividade, utilizando teoria dos grafos. Ap os a explana c~ao de conceitos b asicos, introduzimos a no c~ao de conexidade, demonstrando o teorema de Menger e apresentamos o teorema de Festinger, que e uma ferramenta util para contagem de caminhos. Apresentamos tamb em uma aplica c~ao destes conceitos na an alise da rede de subdistribui c~ao el etrica do estado de Sergipe. Ao nal, concluimos o presente trabalho, propondo algumas sequ^encias did aticas para alunos do ensino m edio abordando o teorema de Euler para grafos, os temas sobre conexidade, conectividade, o teorema de Menger e o teorema de Festinger.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-04-30T13:50:06Z No. of bitstreams: 2 Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf: 631835 bytes, checksum: 92e31eb230a1e5640350250db336b352 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-04-30T13:54:17Z (GMT) No. of bitstreams: 2 Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf: 631835 bytes, checksum: 92e31eb230a1e5640350250db336b352 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-04-30T13:54:17Z (GMT). No. of bitstreams: 2 Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf: 631835 bytes, checksum: 92e31eb230a1e5640350250db336b352 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-10-01 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / In this thesis, we present some results concerning about the sizes of maximal independent sets in graphs. We prove that for integers r and D with r 2 and D 3, there are only finitely many connected graphs of minimum degree at least 2, maximum degree at most D, and girth at least 7 that have maximal independent sets of at most r different sizes. Furthermore, we prove several results restricting the degrees of such graphs. These contributions generalize known results on well-covered graphs. We study the structure and recognition of the well-covered graphs G with order n(G) without an isolated vertex that have independence number n(G)􀀀k 2 for some non-negative integer k. For k = 1, we give a complete structural description of these graphs, and for a general but fixed k, we describe a polynomial time recognition algorithm. We consider graphs G without an isolated vertex for which the independence number a(G) and the independent domination number i(G) satisfy a(G) 􀀀 i(G) k for some non-negative integer k. We obtain a upper bound on the independence number in these graphs. We present a polynomial algorithm to recognize some complementary products, which includes all complementary prisms. Also, we present results on well-covered complementary prisms. We show that if G is not well-covered and its complementary prism is well-covered, then G has only two consecutive sizes of maximal independent sets. We present an upper bound for the quantity of sizes of maximal independent sets in complementary prisms and other wellcovered concerning results. We present a lower bound for the quantity of different sizes of maximal independent sets in Cartesian products of paths and cycles. / Nesta tese, apresentamos alguns resultados relacionados, principalmente, aos tamanhos de conjuntos independentes maximais em alguns grafos. Mostramos que para inteiros r e D, com r 2 e D 3, há um número finito de grafos conexos de grau mínimo pelo menos 2, grau máximo até D e cintura pelo menos 7 que têm tamanhos de conjuntos independentes maximais de até r tamanhos diferentes. Além disso, provamos outros resultados que restringem os graus de tais grafos e que generalizam resultados já conhecidos sobre grafos bem-cobertos. Foram estudados a estrutura e o reconhecimento dos grafos bem-cobertos G de ordem n(G) sem vértice isolado que têm número de independência n(G)􀀀k 2 , para algum inteiro não negativo k. Para k = 1, apresentamos uma descrição estrutural completa destes grafos e para um k geral, porém fixo, descrevemos um algoritmo de complexidade polinomial de tempo para o reconhecimento de tais grafos. Consideramos grafos G sem vértice isolado cuja diferença entre o maior e o menor conjuntos independentes maximais é no máximo k, para algum inteiro k não negativo. Obtivemos um limite superior sobre o número de independência destes grafos. Apresentamos um algoritmo de complexidade polinomial de tempo para reconhecimento de alguns produtos complementares, o qual inclui todos os prismas complementares. Apresentamos também alguns resultados sobre prismas complementares bem-cobertos. Mostramos que se G não é um grafo bem-coberto e seu prisma complementar é bem-coberto, então G tem somente dois tamanhos de conjuntos independentes maximais que são consecutivos. Apresentamos um limite superior para a quantidade de tamanhos de conjuntos independentes maximais em prismas complementares e também outros resultados relacionados à bem-cobertura. Apresentamos um limite inferior para a quantidade de conjuntos independentes maximais de tamanhos diferentes em produtos Cartesianos de caminhos e ciclos.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Os conceitos de DecomposiÃÃo em Ãrvore e Largura em Ãrvore foram introduzidos por Robertson e Seymour em sua sÃrie de artigos sobre menores de grafos, publicados ao longo da dÃcada de 90. Sabe-se que muitos problemas NP - difÃceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposiÃÃo em Ãrvore de G de largura limitada. Logo, limitar a largura em Ãrvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras mÃtricas limitadas em valores baixos (por exemplo, nÃmero cromÃtico), nÃo possui largura em Ãrvore limitada. Desta forma, uma alternativa à restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nÃs investigamos a classe dos grafos planares livres de buracos pares. NÃs mostramos que se G à um grafo planar livre de buracos pares, entÃo ele nÃo contÃm uma subdivisÃo de uma grade 10  10. Portanto, se os menores grades de G sÃo obtidos de subdivisÃes G tem largura em Ãrvore no mÃximo 49. AlÃm disso, dois algoritmos nÃo exatos polinomiais para computar uma decomposiÃÃo em Ãrvore de um grafo planar livre de buracos pares sÃo apresentados, ambos baseados em caracterizaÃÃes conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposiÃÃo em Ãrvore à construÃda a partir de grafos bÃsicos pela concatenaÃÃo de decomposiÃÃes em Ãrvores de pedaÃos pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposiÃÃo em Ãrvore à construÃda pela inclusÃo dos vÃrtices de G um a um, seguindo sua ordem bi-simplicial. / The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10Â10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the Ârst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-05-08T18:41:59Z No. of bitstreams: 1 chrishebertdejesusfranco.pdf: 4880715 bytes, checksum: 5acf9659d9521fbd8fff7e658b785953 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-05-17T14:04:17Z (GMT) No. of bitstreams: 1 chrishebertdejesusfranco.pdf: 4880715 bytes, checksum: 5acf9659d9521fbd8fff7e658b785953 (MD5) / Made available in DSpace on 2017-05-17T14:04:17Z (GMT). No. of bitstreams: 1 chrishebertdejesusfranco.pdf: 4880715 bytes, checksum: 5acf9659d9521fbd8fff7e658b785953 (MD5) Previous issue date: 2014-07-18 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho de dissertação de mestrado versou a síntese e a caracterização estrutural e topológica de quatro novos polímeros de coordenação denominados como Zn-psb, Mn-psb, Cu-psb e Ni-btc com os metais da primeira série de transição (Zn+2, Mn+2, Cu+2 e Ni+2) contendo os ligantes sal ácido 4-sulfobenzoato de monopotássio (H-psb) e ácido 1,2,4-benzenotricarboxilico (4-btc). Além de dois outros compostos poliméricos (Co-btc e Cu-pza) já descritos na literatura. Os compostos foram caracterizados por técnicas espectroscópicas (Infravermelho e Raman) e análise elementar (CHN). A espectroscopia vibracional foi utilizada para apreender sobre os modos de coordenação dos grupos carboxilatos nos compostos com o ligante 4-btc por meio do cálculo do Δѵ [ ѵα(COO) – ѵs(COO) ], em que um estudo da simetria por meio da análise de coordenada normal permitiu uma atribuição mais rigorosa para os modos de coordenação para os grupos SO3 nos compostos derivados do ligante (H-psb). Uma adaptação da técnica de cristalização em gel foi utilizada. Os resultados da análise de CHN evidenciaram que a utilização do agente de cristalização cloridrato de etambutol levou a formação de impurezas na superfície dos compostos Zn-psb e Mn-psb que foram eliminadas durante o processo de cristalização. Os dados de análise térmica (TG/DTA) foram utilizados como dado complementar para caracterização estrutural do composto Ni-btc. As estruturas dos quatro compostos foram determinadas por difração de raios X por monocristal, onde foi possível verificar que a estrutura cristalina do composto Cu-psb encontra-se com uma desordem posicional com fração 54:46 para o anel e oΔѵ grupo SO3, enquanto o monocristal do composto Ni-btc apresenta se geminado com fração 49:51 para os domínios. A solução da estrutura geminada foi dificultada devido à contribuição similar dos domínios formados. Através da difração de raios X por policristais foi possível refinar o modelo estrutural proposto para o composto Ni-btc por meio do método de Rietveld. A descrição topológica desses compostos foi feita utilizando teoria gráfica, sendo que algumas definições e termos foram apresentados. Apesar da semelhança estrutural, o composto Zn-psb apresentou uma rede do tipo tfz-d enquanto o composto Mn-psb apresentou uma rede do tipo pcu. / This work shows the synthesis, structural and topological characterization of four new coordination polymers described as Zn-psb , Mn-psb, Cu-psb and Ni-btc with metals of the first row transition metal ions (Zn+2, Mn+2, Cu+2 and Ni+2) and 4-sulphobenzoate monopotassium (Hpsb), 1,2,4- benzenetricarboxylic acid (4-btc) as ligands. And another two polimeric componds (Co-btc and Cu-pza) described in the literature. The compounds were characterized by spectroscopic techniques (infrared and Raman) and elemental analysis (CHN) where thermal analysis (TG/DTA) were only used for structural characterization of the compound Ni-btc. The vibrational spectroscopy was used to understand the coordination modes of the carboxylate groups in the compounds with 4-btc ligand by analyze of Δѵ values [ ѵα(COO) – ѵs(COO) ]. A study of symmetry by analysis of normal coordinates allowed a rigorous assignment to coordination modes for SO3 groups in the compounds derived H-psb ligand. An adaptation of the technique of crystallization in gel was used. The results of CHN showed that the use of ethambutol hydrochloride as a crystallization agent led to formation of impurities on the surface of the Zn-psb and Mn-psb compounds that was eliminated during the crystallization process. The structures of the four compounds were determined for X-ray diffraction by single crystal, where it was observed that the crystal structure of the compound Cu-psb displays a positional disorder with a fraction of 54:46 for the ring and SO3 group, while the single crystal of the compound Ni-btc was twinned with a fraction of 49:51 for the each domain. The solution of structure was complicated due a similar contribution from domains formed. X-ray diffraction by polycrystals was used like a tool for give a support to refine the structural model proposed for the compound Ni-btc by the Rietveld method. The topological description of these compounds was performed using graph theory where some definitions and terms were presented. Despite the structural similarity, the compound Zn-psb displayed a network of type tfz-d while Mn-psb compound showed a net of type pcu.

Orientador: Marco Antonio Garcia de Carvalho / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-22T22:09:46Z (GMT). No. of bitstreams: 1 Costa_AndreLuisda_M.pdf: 6614237 bytes, checksum: b36b41dce03cbb78f037ec20725bddd2 (MD5) Previous issue date: 2013 / Resumo: O problema de segmentação de colônias de bactérias em placas de Petri possui algumas características bem distintas daquelas encontradas, por exemplo, em problemas de segmentação de imagens naturais. A principal característica é o alto número de colônias que podem ser encontradas em uma placa. Desta forma, é primordial que o algoritmo de segmentação seja capaz de realizar a segmentação da imagem em um grande número de regiões. Este cenário extremo é ideal para analisar limitações dos algoritmos de segmentação. De fato, neste trabalho foi verificado que o algoritmo de corte normalizado original, que se fundamenta na teoria espectral de grafos, é inadequado para aplicações que exigem que a segmentação seja realizada em um grande número de regiões. Contudo, a utilização do critério de corte normalizado para segmentar imagens de colônias de bactérias ainda é possível graças a um novo algoritmo que está sendo introduzido neste trabalho. O novo algoritmo fundamenta-se no agrupamento hierárquico dos nós do grafo, ao invés de utilizar conceito da teoria espectral. Experimentos mostram também que o biparticionamento de um grafo pelo novo algoritmo apresenta um valor de corte normalizado médio cerca de 40 vezes menor que o biparticionamento pelo algoritmo baseado na teoria espectral / Abstract: The problem of bacteria colonies segmentation in Petri dishes has some very different characteristics from those found, for example, in segmenting natural images. The main feature is the high number of colonies that can be found on a plate. Thus, it is essential that the segmentation algorithm is capable of performing the image segmentation into a huge number of regions. This extreme scenario is ideal for analyzing segmentation algorithms limitations. In fact, this study showed that the original normalized cut algorithm, which is based on the spectral graph theory, is inappropriate for applications that require that the segmentation be performed on a large number of regions. However, the use of normalized cut criteria for segmenting bacteria colonies images is still possible thanks to a new algorithm that is being introduced in this paper. The new algorithm is based on hierarchical clustering of the graph nodes, instead of using the spectral theory concepts. Experiments also show that the bi-partitioning of a graph by the new algorithm has a normalized cut average value about 40 times lesser than the bi-partitioning by the algorithm based on the spectral theory / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Orientador: Christiane Neme Campos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:02:03Z (GMT). No. of bitstreams: 1 Galvao_KaioKaram_M.pdf: 1971760 bytes, checksum: e2f60ab09595b03fa6da5051cd78e3f3 (MD5) Previous issue date: 2013 / Resumo: Em 1971, Fulkerson propôs a seguinte conjetura: todo grafo cúbico sem arestas de corte admite seis emparelhamentos perfeitos tais que cada aresta do grafo pertence a exatamente dois destes emparelhamentos. A Conjetura de Fulkerson tem desafiado pesquisadores desde sua publicação. Esta conjetura é facilmente verificada para grafos cúbicos 3-aresta-coloráveis. Portanto, a dificuldade do problema reside em estabelecer a conjetura para grafos cúbicos sem arestas de corte que não possuem 3-coloração de arestas. Estes grafos são chamados snarks. Nesta dissertação, a Conjetura de Fulkerson e os snarks são introduzidos com ¿ênfase em sua história e resultados mais relevantes. Alguns resultados relacionados à Conjetura de Fulkerson são apresentados, enfatizando suas conexões com outras conjeturas. Um breve histórico do Problema das Quatro Cores e suas relações com snarks também são apresentados. Na segunda parte deste trabalho, a Conjetura de Fulkerson é verificada para algumas famílias infinitas de snarks construídas com o método de Loupekine, utilizando subgrafos do Grafo de Petersen. Primeiramente, mostramos que a família dos LP0-snarks satisfaz a Conjetura de Fulkerson. Em seguida, generalizamos este resultado para a família mais abrangente dos LP1-snarks. Além disto, estendemos estes resultados para Snarks de Loupekine construídos com subgrafos de snarks diferentes do Grafo de Petersen / Abstract: In 1971, Fulkerson proposed a conjecture that states that every bridgeless cubic graph has six perfect matchings such that each edge of the graph belongs to precisely two of these matchings. Fulkerson's Conjecture has been challenging researchers since its publication. It is easily verified for 3-edge-colourable cubic graphs. Therefore, the difficult task is to settle the conjecture for non-3-edge-colourable bridgeless cubic graphs, called snarks. In this dissertation, Fulkerson's Conjecture and snarks are presented with emphasis in their history and remarkable results. We selected some results related to Fulkerson's Conjecture, emphasizing their reach and connections with other conjectures. It is also presented a brief history of the Four-Colour Problem and its connections with snarks. In the second part of this work, we verify Fulkerson's Conjecture for some infinite families of snarks constructed with Loupekine's method using subgraphs of the Petersen Graph. More specifically, we first show that the family of LP0-snarks satisfies Fulkerson's Conjecture. Then, we generalise this result by proving that Fulkerson's Conjecture holds for the broader family of LP1-snarks. We also extend these results to even more general Loupekine Snarks constructed with subgraphs of snarks other than the Petersen Graph / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Akebo Yamakami, Ricardo Coelho Silva / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-19T06:43:21Z (GMT). No. of bitstreams: 1 Ciappina_JussaraRodrigues_D.pdf: 6752680 bytes, checksum: 3dcb7910cc5098e44936e76045792069 (MD5) Previous issue date: 2011 / Resumo: Este trabalho apresenta dois métodos baseados no método clássico de decomposição de Dantzig-Wolfe e um método heurístico, os quais resolvem problemas com incertezas nos parâmetros utilizando a teoria dos conjuntos fuzzy. O primeiro aborda incertezas somente nos custos, enquanto que, os outros dois abordam incertezas nos custos e nas restrições. Métodos que utilizam técnicas de decomposição são indicados para resolver problemas de grande porte que apresentam uma estrutura especial em uma parte do conjunto das restrições. Um exemplo de problema que apresenta tal estrutura é o problema de fluxo multiproduto. Este problema pode ser modelado através de um grafo, cujos nós representam pontos de oferta, demanda e passagem de produtos que trafegam pelos arcos da rede. O objetivo é determinar o fluxo de cada produto nos arcos, de modo a atender a demanda a um custo mínimo, respeitando as restrições de capacidade dos arcos e as restrições de conservação de fluxo dos nós. Com exceção do terceiro, os demais métodos propostos neste trabalho não se limitam a resolver problemas de fluxo multiproduto fuzzy, também resolvem problemas de programação linear fuzzy que apresentam uma estrutura especial em uma parte do conjunto das restrições / Abstract: In this work we present two methods based in the classical Dantzig-Wolfe decomposition and a heuristic method, which solve problems with uncertainties in the parameters using the theory of fuzzy sets. The first one deals with uncertainties only in costs, while the others two deal with uncertainties in costs and restrictions. Methods using decomposition techniques address problems that have a special structure in the set of restrictions. An example of such a problem that has this structure is the fuzzy multicommodity flow problem. This problem can be modeled by a graph whose nodes represent points of supply, demand and passage of commodities that travel by the arcs of the network. The objective is to determine the flow of each commodity in the arcs, in order to meet demand at a minimal cost while respecting the capacity restrictions of the arcs and the flow conservation restrictions of the nodes. With the exception of the third, the other methods proposed in this work are not limited to solve fuzzy multicommodity flow problems, also solve fuzzy linear programming problems that have a special structure in a part of the set of restrictions / Doutorado / Automação / Doutor em Engenharia Elétrica

Orientador: Andre Luiz Morelato França / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-04T08:13:24Z (GMT). No. of bitstreams: 1 Mota_AlexandredeAssis_D.pdf: 2550000 bytes, checksum: d1b87870a85e6720b234c4e11cce99a8 (MD5) Previous issue date: 2005 / Resumo: O sucesso da recomposição de sistemas interligados está diretamente associado à qualidade dos planos de recomposição. Esses planos descrevem as seqüências de ações de controle que devem ser tomadas para energizar as diferentes áreas geoelétricas do sistema após a ocorrência de blecautes totais ou parciais. Nesse contexto, o objetivo deste trabalho é propor uma metodologia para avaliação da qualidade de planos de recomposição, que permita o uso de ferramentas computacionais para avaliar a qualidade de forma automática e sob alguns critérios como (a) grau de flexibilidade quanto a imprevistos durante a execução, (b) índices de qualidade globais determinados a partir da representação do plano de recomposição através de grafos conexos e (c) facilidade de acesso, visualização, atualização e treinamento. Diferentes técnicas e métodos foram empregados para atingir esse objetivo (busca de caminho mínimo, utilização de índices nebulosos, métodos de caminho crítico - CPM/PERT), visando a determinação dos índices numéricos relacionados à qualidade do plano, tais como: duração total prevista para a recomposição, eficiência da fase fluente, evolução da carga interrompida e custos estimados para a interrupção / Abstract: A successful restoration depends on the quality of the restoration plans, that describe the sequence of control actions that must be executed to reenergize different areas (of the power system) just after total or partial blackouts. This work proposes a methodology to automatically evalute the quality of power system restoration plans, related to (a) the flexibility of the plan, (b) numerical quality indexes, extracted using a graph representation for the plan and (c) the easiness of use, visualization, training and access to restoration instructions. Different techniques and methods were used to achieve this goal (minimum path search, adoption of fuzzy indexes, critical path methods), focusing on the determination of numerical indexes that express the quality of the plan, such as total restoration duration, fluent phase efficiency, interrupted load evolution and estimated interruption costs / Doutorado / Energia Eletrica / Doutor em Engenharia Elétrica

Molecular biology has entered an era of systematic and automated experimentation. High-throughput techniques have moved biology from small-scale experiments focused on specific genes and proteins to genome and proteome-wide screens. One result of this endeavor is the compilation of complex networks of interacting proteins. Molecular biologists hope to understand life's complex molecular machines by studying these networks. This thesis addresses tree open problems centered upon their analysis and quality assessment. First, we introduce power graph analysis as a novel approach to the representation and visualization of biological networks. Power graphs are a graph theoretic approach to lossless and compact representation of complex networks. It groups edges into cliques and bicliques, and nodes into a neighborhood hierarchy. We demonstrate power graph analysis on five examples, and show its advantages over traditional network representations. Moreover, we evaluate the algorithm performance on a benchmark, test the robustness of the algorithm to noise, and measure its empirical time complexity at O (e1.71)- sub-quadratic in the number of edges e. Second, we tackle the difficult and controversial problem of data quality in protein interaction networks. We propose a novel measure for accuracy and completeness of genome-wide protein interaction networks based on network compressibility. We validate this new measure by i) verifying the detrimental effect of false positives and false negatives, ii) showing that gold standard networks are highly compressible, iii) showing that authors' choice of confidence thresholds is consistent with high network compressibility, iv) presenting evidence that compressibility is correlated with co-expression, co-localization and shared function, v) showing that complete and accurate networks of complex systems in other domains exhibit similar levels of compressibility than current high quality interactomes. Third, we apply power graph analysis to networks derived from text-mining as well to gene expression microarray data. In particular, we present i) the network-based analysis of genome-wide expression profiles of the neuroectodermal conversion of mesenchymal stem cells. ii) the analysis of regulatory modules in a rare mitochondrial cytopathy: emph{Mitochondrial Encephalomyopathy, Lactic acidosis, and Stroke-like episodes} (MELAS), and iii) we investigate the biochemical causes behind the enhanced biocompatibility of tantalum compared with titanium.

The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following work, we look at the other end of the spectrum where in our goal is to maximize the number of colors used for coloring the edges of the graph under some vertex specific constraints. We deal with the MAXIMUM EDGE COLORING problem which is defined as the following –For an integer q ≥2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. The question is very well motivated by the problem of channel assignment in wireless networks. This problem is NP-hard for q ≥ 2, and has been well-studied from the point of view of approximation. This problem has not been studied in the parameterized context before. Hence as a next step, this thesis investigates the parameterized complexity of this problem where the standard parameter is the solution size. The main focus of the work is the special case of q=2 ,i.e. MAXIMUM EDGE 2-COLORING which is theoretically intricate and practically relevant in the wireless networks setting. We first show an exponential kernel for the MAXIMUM EDGE q-COLORING problem where q is a fixed constant and q ≥ 2.We do a more specific analysis for the kernel of the MAXIMUM EDGE 2-COLORING problem. The kernel obtained here is still exponential in size but is better than the kernel obtained for MAXIMUM EDGE q-COLORING problem in case of q=2. We then show a fixed parameter tractable algorithm for the MAXIMUM EDGE 2-COLORING problem with a running time of O*∗(kO(k)).We also show a fixed parameter tractable algorithm for the MAXIMUM EDGE q-COLORING problem with a running time of O∗(kO(qk) qO(k)). The fixed parameter tractability of the dual parametrization of the MAXIMUM EDGE 2-COLORING problem is established by arguing a linear vertex kernel for the problem. We also show that the MAXIMUM EDGE 2-COLORING problem remains hard on graphs where the maximum degree is a constant and also on graphs without cycles of length four. In both these cases, we obtain quadratic kernels. A closely related variant of the problem is the question of MAX EDGE{1,2-}COLORING. For this problem, the vertices in the input graph may have different qε,{1.2} values and the goal is to use at least k colors for the edge coloring of the graph such that every vertex sees at most q colors, where q is either one or two. We show that the MAX EDGE{1,2}-COLORING problem is W[1]-hard on graphs that have no cycles of length four.