Academic literature on the topic 'Emparelhamento de grafos bipartidos'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Emparelhamento de grafos bipartidos.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Emparelhamento de grafos bipartidos"
1
Pereira, Alessandra Aparecida, and Carmen Cecilia Centeno. "Reformulação de Estratégia de Aliança Defensiva e Ofensiva em Grafos." Revista Arithmós - Revista da Escola de Ciências Exatas e da Computação 1, no. 1 (June 26, 2019): 33. http://dx.doi.org/10.18224/arithmos.v1i1.6893.
Full textAbstract:
Neste trabalho é proposto um novo problema chamado de reformulação de estratégia de alianças, onde a aliança defensiva se transforma em uma aliança ofensiva que contém os vértices da aliança defensiva de origem, e vice-versa. O objetivo é reformular a estratégia de aliança defensiva e ofensiva de cardinalidade mínima para algumas classes de grafos como caminhos, ciclos, rodas, grafos completos, bipartidos completos, estrela e árvores binárias balanceadas.
2
Cortez Morales, Walter Julio. "Uma caracterização de grafos imersíveis." Pesquisa Operacional 25, no. 1 (April 2005): 1–9. http://dx.doi.org/10.1590/s0101-74382005000100001.
Full textAbstract:
Este trabalho é motivado pelo resultado de Berge, que é uma generalização do teorema de Tutte o qual expressamos na forma: Dado o grafo G de ordem |V(G)| eni(G) o número de arestas em um emparelhamento máximo, existe um conjunto X de vértices de G tal que |V(G)|+|X| - ômega(G\X) - 2n(G)=0, onde ômega(G\X) é o número de componentes de ordem ímpar de G\X. Tal expressão chamamos a equação de Tutte-Berge associada de G, e escrevemos simplesmente T(G; X)=0. Os grafos podem ser classificados a partir das soluções da equação de Tutte-Berge. Um grafo G é chamado imersível se, e somente se, T(G; X)=0 possui pelo menos um conjunto solução não vazio de vértices, e G é denominado não imersível se, e somente se, o conjunto vazio é a única solução de T(G; X)=0. O resultado principal deste artigo é a caracterização de grafos imersíveis pelos conjuntos antifatores completos, além disso, provamos que os grafos fatoráveis estão contidos na classe dos imersíveis.
3
Silva, Gheyza Ferreira da, Mercio Botelho Faria, and Catarina Mendes de Jesus. "Grafos que geram emparelhamento de arestas relacionados à Tesselação $\{12g-6, 3\}$." TEMA (São Carlos) 15, no. 2 (September 6, 2014). http://dx.doi.org/10.5540/tema.2014.015.02.0151.
Full textDissertations / Theses on the topic "Emparelhamento de grafos bipartidos"
1
Saip, Herbert Alexander Baier. "Algoritmos para emparelhamentos em grafos bipartidos." [s.n.], 1993. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275967.
Full textAbstract:
Orientador : Claudio Leonardo LucchesiDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação
Made available in DSpace on 2018-07-18T08:17:24Z (GMT). No. of bitstreams: 1 Saip_HerbertAlexanderBaier_M.pdf: 3945244 bytes, checksum: af2897a4f350aea0252f42478c71f837 (MD5) Previous issue date: 1993
Resumo: O problema de emparelhamentos em grafos consiste em determinar um conjunto M de arestas do grafo, onde as arestas são disjuntas nos vértices. Em particular, estamos interessados em determinar emparelhamentos máximos, ou seja, de cardinalidade máxima. Existem muitas variações em torno do tema, o grafo pode ser: bipartido ou não, ponderado ou não. Neste trabalho apresentamos as principais técnicas para se projetar os algoritmos mais eficientes que resolvem o problema de emparelhamentos máximos, ponderados ou não, em grafos bipartidos. Também descrevemos os principais algoritmos, seqüenciais e paralelos, que resolvem este problema. O Capítulo 2 apresenta os principais algoritmos para resolver o problema em grafos bipartidos não ponderados: o algoritmo de Hopcroft e Karp, o algoritmo paralelo de Kim e Chwa e o algoritmo paralelo de Goldberg, Plotkin e Vaidya. O Capítulo 3 apresenta os principais algoritmos para resolver o problema em grafos bipartidos ponderados: o algoritmo de Edmonds e Karp, o algoritmo com escalonamento de Gabow, o algoritmo com escalonamento e aproximação de Gabow e Tarjan, o algoritmo paralelo de Goldberg, Plotkin e Vaidya e o algoritmo paralelo de Gabow e Tarjan. O Apêndice A contém uma tabela dos principais algoritmos para resolver o problema no caso em que os grafos não são bipartidos
Abstract: The matching problem in graphs consists in determining a vertex disjoint set M of edges of the graph. In particular, we are interested in finding maximum matchings, that is, matchings of maximum cardinality. There are many variations around this problem, the graph can be: bipartite or general, weighted or not. In this work we present the main techniques to design the most efficient algorithms that solve the problem of maximum matching, weighted or not, in bipartite graphs. We also describe the main algorithms, sequential and parallel, to solve this problem. Chapter 2 contains the most important algorithms to solve the problem for non weighted bipartite graphs, namely, the algorithm of Hopcroft and Karp, the parallel algorithm of Kim and Chwa, and the parallel algorithm of Goldberg, Plotkin and Vaidya. Chapter 3 contains the most important algorithms to solve the problem for weighted bipartite graphs, namely, the algorithm of Edmonds and Katp, the scaling algorithm of Gabow, the scaling and approximation algorithm of Gabow and Tarjan, the parallel algorithm of Goldberg, Plotkin and Vaidya and the parallel algorithm of Gabow and Tarjan. In Appendix A it is given a table which describes briefly the most important algorithms for solving the general problem, in which the graph is not bipartite
Mestrado
Mestre em Ciência da Computação
2
Silva, Candida Nunes da. "A conjetura dos 3-fluxos de Tutte e emparelhamentos em grafos bipartidos." [s.n.], 2001. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276439.
Full textAbstract:
Orientador : Ricardo DahabDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-07-28T09:27:15Z (GMT). No. of bitstreams: 1 Silva_CandidaNunesda_M.pdf: 9020782 bytes, checksum: 72d783f2186f3848f226c74b427014de (MD5) Previous issue date: 2001
Mestrado
3
Ferreira, Verônica Craveiro de Santana. "De grafos a emparelhamentos : uma possibilidade viável de encantar-se com a matemática." Universidade Federal de Sergipe, 2014. https://ri.ufs.br/handle/riufs/6510.
Full textAbstract:
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESThis thesis aims to show that the theory of graphs, especially matching, can be studied in high school and gradually as the implementation of this theory in the classroom can foster in students interest in mathematics. Thus, this paper aims to demystify the idea that mathematics content ends with high school approaching students the theories recently developed in academy. The graph theory is considered an e cient tool to solve problems in various areas. There are numerous situations that can be modeled by that enable develop a range of skills, so it becomes so appealing to anyone who comes into contact with it. For the development of this thesis began our study addressing basic concepts of graph theory useful for understanding this work then present some problems that can be worked in high school and nalized with a speci c topic of this theory, matchings, with many applications that can be modeled as contextualized and practical problems of everyday life.
A presente disserta ção tem como objetivo mostrar que a teoria de grafos, sobretudo emparelhamentos, pode ser abordada no ensino m édio de forma gradativa. E como a implementa ção desta teoria em sala de aula pode despertar nos estudantes o interesse pela matem atica. Dessa forma, este trabalho pretende desmitifi car a ideia de que a matem atica se encerra com o conte udo do ensino m édio aproximando os estudantes das teorias desenvolvidas recentemente na academia. A teoria dos grafos é considerada uma ferramenta e ficiente para resolver problemas em diferentes áreas. São in úmeras situa ções que podem ser modeladas por grafos que possibilitam desenvolver uma s érie de habilidades, por isso ela se torna tao atraente para quem entra em contato com a mesma. Para o desenvolvimento desta disserta ção, iniciamos nosso estudo abordando conceitos b ásicos da teoria de grafos úteis a compreensão deste trabalho, em seguida apresentamos alguns problemas que podem ser trabalhados no ensino m édio e a nalisamos com um t ópico específi co desta teoria, emparelhamentos, com muitas aplica coes que podem ser contextualizadas e modeladas como problemas pr áticos do nosso cotidiano.
4
Honda, Willian Yukio. "Rotulação de símbolos matemáticos manuscritos via casamento de expressões." Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-22022013-120830/.
Full textAbstract:
O problema de reconhecimento de expressões matemáticas manuscritas envolve três subproblemas importantes: segmentação de símbolos, reconhecimento de símbolos e análise estrutural de expressões. Para avaliar métodos e técnicas de reconhecimento, eles precisam ser testados sobre conjuntos de amostras representativos do domínio de aplicação. Uma das preocupações que tem sido apontada ultimamente é a quase inexistência de base de dados pública de expressões matemáticas, o que dificulta o desenvolvimento e comparação de diferentes abordagens. Em geral, os resultados de reconhecimento apresentados na literatura restringem-se a conjuntos de dados pequenos, não disponíveis publicamente, e muitas vezes formados por dados que visam avaliar apenas alguns aspectos específicos do reconhecimento. No caso de expressões online, para treinar e testar reconhecedores de símbolos, as amostras são em geral obtidas solicitando-se que as pessoas escrevam uma série de símbolos individualmente e repetidas vezes. Tal tarefa é monótona e cansativa. Uma abordagem alternativa para obter amostras de símbolos seria solicitar aos usuários a transcrição de expressões modelo previamente definidas. Dessa forma, a escrita dos símbolos seria realizada de forma natural, menos monótona, e várias amostras de símbolos poderiam ser obtidas de uma única expressão. Para evitar o trabalho de anotar manualmente cada símbolo das expressões transcritas, este trabalho propõe um método para casamento de expressões matemáticas manuscritas, no qual símbolos de uma expressão transcrita por um usuário são associados aos correspondentes símbolos (previamente identificados) da expressão modelo. O método proposto é baseado em uma formulação que reduz o problema a um problema de associação simples, no qual os custos são definidos em termos de características dos símbolos e estrutura da expressão. Resultados experimentais utilizando o método proposto mostram taxas médias de associação correta superiores a 99%.The problem of recognizing handwritten mathematical expressions includes three important subproblems: symbol segmentation, symbol recognition, and structural analysis of expressions. In order to evaluate recognition methods and techniques, they should be tested on representative sample sets of the application domain. One of the concerns that are being repeatedly pointed recently is the almost non-existence of public representative datasets of mathematical expressions, which makes difficult the development and comparison of distinct approaches. In general, recognition results reported in the literature are restricted to small datasets, not publicly available, and often consisting of data aiming only evaluation of some specific aspects of the recognition. In the case of online expressions, to train and test symbol recognizers, samples are in general obtained asking users to write a series of symbols individually and repeatedly. Such task is boring and tiring. An alternative approach for obtaining samples of symbols would be to ask users to transcribe previously defined model expressions. By doing so, writing would be more natural and less boring, and several symbol samples could be obtained from one transcription. To avoid the task of manually labeling the symbols of the transcribed expressions, in this work a method for handwritten expression matching, in which symbols of a transcribed expression are assigned to the corresponding ones in the model expression, is proposed. The proposed method is based on a formulation that reduces the matching problem to a linear assignment problem, where costs are defined based on symbol features and expression structure. Experimental results using the proposed method show that mean correct assignment rate superior to 99% is achieved.
5
Fonseca, Thiago Silveira da. "Grafos e emparelhamento em grafos." Universidade Federal de Viçosa, 2018. http://www.locus.ufv.br/handle/123456789/19940.
Full textAbstract:
Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2018-06-05T13:32:44Z
No. of bitstreams: 1
texto completo.pdf: 3038671 bytes, checksum: 989b48613d3d2c169a2fc7e19dc661aa (MD5)Made available in DSpace on 2018-06-05T13:32:44Z (GMT). No. of bitstreams: 1 texto completo.pdf: 3038671 bytes, checksum: 989b48613d3d2c169a2fc7e19dc661aa (MD5) Previous issue date: 2018-02-28
Pesquisa desenvolvida a partir das noções sobre grafos, grafos eulerianos, árvores, emparelhamentos em grafos, grafos planares e coloração. Foram abordados alguns dos principais teoremas e lemas, bem como imagens e exemplos para facilitar a leitura. Conclusão da pesquisa com o relato das aulas práticas sobre grafos.
The research was developed based on the notion about graphs, eulerian graphs, trees, matchings in graphs, planar graphs and coloring. Some of the main theorems and lemmas were discussed, as well as images and examples to facilitate reading. The conclusion of the research with the report of the practical classes about graphs.
Sem lattes e agência de fomento.
6
Freire, Alexandre da Silva. "Empacotamento de bicliques em grafos bipartidos." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-26112012-161435/.
Full textAbstract:
Nesta tese, estudamos o problema de Empacotamento de Bicliques. Um biclique é um grafo bipartido completo. No problema de Empacotamento de Bicliques são dados um inteiro k e um grafo bipartido G e deseja-se encontrar um conjunto de k bicliques, subgrafos de G, dois a dois disjuntos nos vértices, tal que a quantidade total de arestas dos bicliques escolhidos seja máxima. No caso em que k=1, temos o problema de Biclique máximo. Esses dois problemas possuem aplicações na área de Bioinformática. Mantemos neste trabalho um enfoque prático, no sentido de que nosso interesse é resolver instâncias desses dois problemas com tamanho razoavelmente grande. Para isso, utilizamos técnicas de Programação Linear Inteira. Para avaliar os métodos propostos aqui, mostramos resultados de experimentos computacionais feitos com instâncias vindas de aplicações e também com instâncias geradas aleatoriamente.In this thesis, we study the Biclique Packing problem. A biclique is a complete bipartite graph. In the Biclique Packing problem we are given an integer k and a bipartite graph G and we want to find a set of k vertex disjoint bicliques of G, such that the total number of biclique\'s edges is maximum. When k=1, we have the Maximum Biclique problem. These two problems have applications in Bioinformatics. In this work we keep a practical focus, in the sense that we are interested in solving large size instances of these problems. To tackle these problems, we use Integer Linear Programming techniques. In order to evaluate the methods proposed here, we show results of computational experiments carried out with practical application\'s instances and also with randomly generated ones.
7
Silva, Gheyza Ferreira da. "Emparelhamento de arestas de polígonos gerados por grafos." Universidade Federal de Viçosa, 2011. http://locus.ufv.br/handle/123456789/4910.
Full textAbstract:
Made available in DSpace on 2015-03-26T13:45:33Z (GMT). No. of bitstreams: 1
texto completo.pdf: 1007963 bytes, checksum: 8fb51039076c92104d50598359cf19d8 (MD5)
Previous issue date: 2011-02-24This work has as main objective the study of side-pairing patterns for hyperbolic polygons with 12g−6 edges and angles 2π/3 generated by trivalent graphs, in the case when the quotient of the hyperbolic plane by a Fuchsian group Γ (generated by the side-pairing of the polygon), H2/Γ , is a closed surface of genus g, g ≥ 2. So we did a study in case of g = 2, based on [10] and for the case of g = 3, based on [17]. In this work, we deduce two ways to get closed paths in the trivalent graphs cited in [10] and [17] and we contribute with exemples and results for cases of g > 3. Moreover, we find generalizations for some of these side-pairing patterns.
Este trabalho tem como objetivo principal o estudo de emparelhamentos de arestas para polígonos hiperbólicos com 12g − 6 arestas e ângulos iguais a 2π/3 gerados por meio de grafos trivalentes, no caso em que o quociente do plano hiperbólico por um grupo Fuchsiano Γ (gerado pelo emparelhamento do polígono), H2/Γ , é uma superfície fechada de gênero g, g ≥ 2. Assim, fizemos um estudo para o caso de g = 2 baseado em [10] e para o caso de g = 3, baseado em [17]. Neste trabalho, nós deduzimos duas formas de obter os caminhos fechados nos grafos trivalentes citados em [10] e [17] e contribuímos com exemplos e resultados para casos em que g > 3. Além disso, encontramos generalizações para alguns desses emparelhamentos de arestas.
8
Cruz, Carlos Fernando Bella. "Algoritmos para emparelhamento em grafos e uma implementação paralela." [s.n.], 1996. http://repositorio.unicamp.br/jspui/handle/REPOSIP/276023.
Full textAbstract:
Orientador: João Carlos SetubalDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da ComputaçãO
Made available in DSpace on 2018-07-21T05:57:00Z (GMT). No. of bitstreams: 1 Cruz_CarlosFernandoBella_M.pdf: 2090300 bytes, checksum: c7ddb8099b731928143e26f66c270afc (MD5) Previous issue date: 1996
Resumo: Abordamos os principais algoritmos para o problema de emparelhamento máximo em grafos genéricos e desenvolvemos uma implementação paralela eficiente na prática, baseada no algoritmo seqüencial de Edmonds. Por prática entendemos uma implementação eficiente num multiprocessador de memória com partilhada. A implementação consiste em permitir que cada processador procure caminhos aumentantes no grafo de forma assíncrona e independente dos demais. Embora a busca ocorra de forma paralela, o aumento do emparelhamento é feito por somente 1 processador por vez, o que garante a corretude do algoritmo sem incorrrer em atraso significativo no tempo de execução. O desenvolvimento da implementação teve como antecedente uma experiência negativa de paralelização baseada no algoritmo de Micali e Vazirani.
Abstract: In this work we present the most important matching algorithms for general graphs and develop an efficient parallel implementation in practice based on Edmonds'matching algorithm. By practice we mean an efficient implementation on a shared memory multiprocessor. The implementation allows each processor to find augmenting paths assinchronously and independently of each other. Each matching augmentation is done by only one processor, and this makes the algorithm correct without causing significant delay in the execution time, in practice. The development of this implementation was made after a nega tive experience of paralelization based on the sequential algorithm of Micali and Vazirani.
Mestrado
Mestre em Ciência da Computação
9
Faleiros, Thiago de Paulo. "Propagação em grafos bipartidos para extração de tópicos em fluxo de documentos textuais." Universidade de São Paulo, 2016. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-10112016-105854/.
Full textAbstract:
Tratar grandes quantidades de dados é uma exigência dos modernos algoritmos de mineração de texto. Para algumas aplicações, documentos são constantemente publicados, o que demanda alto custo de armazenamento em longo prazo. Então, é necessário criar métodos de fácil adaptação para uma abordagem que considere documentos em fluxo, e que analise os dados em apenas um passo sem requerer alto custo de armazenamento. Outra exigência é a de que essa abordagem possa explorar heurísticas a fim de melhorar a qualidade dos resultados. Diversos modelos para a extração automática das informações latentes de uma coleção de documentos foram propostas na literatura, dentre eles destacando-se os modelos probabilísticos de tópicos. Modelos probabilísticos de tópicos apresentaram bons resultados práticos, sendo estendidos para diversos modelos com diversos tipos de informações inclusas. Entretanto, descrever corretamente esses modelos, derivá-los e em seguida obter o apropriado algoritmo de inferência são tarefas difíceis, exigindo um tratamento matemático rigoroso para as descrições das operações efetuadas no processo de descoberta das dimensões latentes. Assim, para a elaboração de um método simples e eficiente para resolver o problema da descoberta das dimensões latentes, é necessário uma apropriada representação dos dados. A hipótese desta tese é a de que, usando a representação de documentos em grafos bipartidos, é possível endereçar problemas de aprendizado de máquinas, para a descoberta de padrões latentes em relações entre objetos, por exemplo nas relações entre documentos e palavras, de forma simples e intuitiva. Para validar essa hipótese, foi desenvolvido um arcabouço baseado no algoritmo de propagação de rótulos utilizando a representação em grafos bipartidos. O arcabouço, denominado PBG (Propagation in Bipartite Graph), foi aplicado inicialmente para o contexto não supervisionado, considerando uma coleção estática de documentos. Em seguida, foi proposta uma versão semissupervisionada, que considera uma pequena quantidade de documentos rotulados para a tarefa de classificação transdutiva. E por fim, foi aplicado no contexto dinâmico, onde se considerou fluxo de documentos textuais. Análises comparativas foram realizadas, sendo que os resultados indicaram que o PBG é uma alternativa viável e competitiva para tarefas nos contextos não supervisionado e semissupervisionado.Handling large amounts of data is a requirement for modern text mining algorithms. For some applications, documents are published constantly, which demand a high cost for long-term storage. So it is necessary easily adaptable methods for an approach that considers documents flow, and be capable of analyzing the data in one step without requiring the high cost of storage. Another requirement is that this approach can exploit heuristics in order to improve the quality of results. Several models for automatic extraction of latent information in a collection of documents have been proposed in the literature, among them probabilistic topic models are prominent. Probabilistic topic models achieve good practical results, and have been extended to several models with different types of information included. However, properly describe these models, derive them, and then get appropriate inference algorithms are difficult tasks, requiring a rigorous mathematical treatment for descriptions of operations performed in the latent dimensions discovery process. Thus, for the development of a simple and efficient method to tackle the problem of latent dimensions discovery, a proper representation of the data is required. The hypothesis of this thesis is that by using bipartite graph for representation of textual data one can address the task of latent patterns discovery, present in the relationships between documents and words, in a simple and intuitive way. For validation of this hypothesis, we have developed a framework based on label propagation algorithm using the bipartite graph representation. The framework, called PBG (Propagation in Bipartite Graph) was initially applied to the unsupervised context for a static collection of documents. Then a semi-supervised version was proposed which need only a small amount of labeled documents to the transductive classification task. Finally, it was applied in the dynamic context in which flow of textual data was considered. Comparative analyzes were performed, and the results indicated that the PBG is a viable and competitive alternative for tasks in the unsupervised and semi-supervised contexts.
10
Costa, Eurinardo Rodrigues. "Convexidade Monofônica em Classes de Grafos." reponame:Repositório Institucional da UFC, 2016. http://www.repositorio.ufc.br/handle/riufc/16736.
Full textAbstract:
COSTA, Eurinardo Rodrigues. Convexidade Monofônica em Classes de Grafos. 2016. 54 f. Dissertação (mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2016.Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-03-22T19:02:45Z No. of bitstreams: 1 2016_dis_ercosta.pdf: 1611008 bytes, checksum: 4733a7aa273b8370fc06126fca5dc15a (MD5)
Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-05-12T11:58:17Z (GMT) No. of bitstreams: 1 2016_dis_ercosta.pdf: 1611008 bytes, checksum: 4733a7aa273b8370fc06126fca5dc15a (MD5)
Made available in DSpace on 2016-05-12T11:58:17Z (GMT). No. of bitstreams: 1 2016_dis_ercosta.pdf: 1611008 bytes, checksum: 4733a7aa273b8370fc06126fca5dc15a (MD5) Previous issue date: 2016
In this work, we study some parameters of monophonic convexity in some classes of graphs and we present our results about this subject. We prove that decide if the $m$-interval number is at most 2 and decide if the $m$-percolation time is at most 1 are NP-complete problems even on bipartite graphs. We also prove that the $m$-convexity number is as hard to approximate as the maximum clique problem, which is, $O(n^{1-varepsilon})$-unapproachable in polynomial-time, unless P=NP, for each $varepsilon>0$. Finally, we obtain polynomial time algorithms to compute the $m$-convexity number on hereditary graph classes such that the computation of the clique number is polynomial-time solvable (e.g. perfect graphs and planar graphs).
Neste trabalho, estudamos alguns parâmetros para a convexidade monofônica em algumas classes de grafos e apresentamos nossos resultados acerca do assunto. Provamos que decidir se o número de $m$-intervalo é no máximo 2 e decidir se o tempo de $m$-percolação é no máximo 1 são problemas NP-completos mesmo em grafos bipartidos. Também provamos que o número de $m$-convexidade é tão difícil de aproximar quanto o problema da Clique Máxima, que é, $O(n^{1-varepsilon})$-inaproximável em tempo polinomial, a menos que P=NP, para cada $varepsilon>0$. Finalmente, apresentamos um algoritmo de tempo polinomial para determinar o número de $m$-convexidade em classes hereditárias de grafos onde a computação do tamanho da clique máxima é em tempo polinomial (como grafos perfeitos e grafos planares).
Conference papers on the topic "Emparelhamento de grafos bipartidos"
1
Gomes, Guilherme de C. M., Bruno P. Masquio, Paulo E. D. Pinto, Vinicius F. Santos, and Jayme L. Szwarcfiter. "Emparelhamento Desconexo é NP-Completo." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16372.
Full textAbstract:
Um subconjunto M ⊆ E de arestas de um grafo G = (V, E) é um emparelhamento se nenhum par de arestas de M compartilha um vértice comum. Recentemente, P-emparelhamentos foram propostos, os quais requerem algumas propriedades dos subgrafos induzidos pelos vértices M-saturados de G. Tratamos um deles, o problema do emparelhamento desconexo, cuja propriedade é que o referido subgrafo induzido seja desconexo. Embora alguns algoritmos eficientes já tenham sido mostrados para algumas classes, a complexidade do problema geral permanecia em aberto. Apresentamos uma prova de que o emparelhamento desconexo é NP-completo, mesmo para grafos bipartidos e grafos com diâmetro limitado.
2
C. Sena, Alexandre, Aline Nascimento, Cristina Vasconcelos, and Leandro A. J. Marzulo. "Execução Eficiente do Algoritmo de Leilão nas Novas Arquiteturas Multicore." In XVIII Simpósio em Sistemas Computacionais de Alto Desempenho. Sociedade Brasileira de Computação, 2017. http://dx.doi.org/10.5753/wscad.2017.240.
Full textAbstract:
O algoritmo de leilão tem sido amplamente utilizado para resolver o problema de emparelhamento de grafos bipartidos e sua implementação paralela é empregada para encontrar soluções ótimas em um tempo computacional aceitável. Além disso, as novas arquiteturas multicore, além de seus vários núcleos de processamento, possuem um conjunto de instruções SIMD que pode aumentar o desempenho da aplicação quando exatamente as mesmas operações necessitam ser realizadas em múltiplos dados. Nesse contexto, o objetivo deste trabalho é explorar todo o potencial dessas arquiteturas na execução do algoritmo de leilão. Para alcançar este objetivo, versões vetorizadas foram implementadas e avaliadas. Em seguida, essas versões foram executadas em paralelo utilizando a biblioteca OpenMP. Os resultados mostram que a versão vetorizada consegue, em média, um desempenho dez vezes melhor que a versão sequencial, enquanto a versão vetorizada paralela é capaz de aproveitar todo o potencial das novas arquiteturas multicore, atingindo um desempenho até 200 vezes melhor do que a versão sequencial.
3
Sucupira, Rubens A., Sulamita Klein, and Luerbio Faria. "Half Cuts em Grafos Bipartidos Completos." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3161.
Full textAbstract:
Um grafo é Half Cut se admite um corte de arestas de cardinalidade d m2 e. É sabido que grafos graciosos são Half Cut e os grafos bipartidos completos são graciosos. Neste artigo damos uma prova alternativa de que os grafos bipartidos completos são Half Cut, exibindo um corte de arestas de cardinalidade d m2 e.
4
Gómez, Renzo. "Vertex-disjoint path covers in graphs." In II Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3205.
Full textAbstract:
Seja G um grafo conexo e P um conjunto de caminhos disjuntos nos vértices em G. Dizemos que P é uma cobertura por caminhos se cada vértice de G pertence a algum caminho em P . No problema da cobertura mínima por caminhos, o objetivo é encontrar uma cobertura com o menor número de caminhos. Nesse problema, que é sabido ser NP-difícil, o conjunto P pode conter caminhos triviais. Estudamos uma variante desse problema onde o objetivo é encontrar uma cobertura sem caminhos triviais. Usando a decomposição de Edmonds-Gallai, mostramos que o problema de decidir se um grafo tem tal cobertura pode ser reduzido a um problema de emparelhamento em um grafo bipartido. Além disso, mostramos resultados de inaproximabilidade para ambos os problemas de cobertura: com e sem caminhos triviais.
5
Bornstein, Claudson F., José Wilson C. Pinto, and Jayme L. Szwarcfiter. "Grafos Bipartidos Completos em ORTH[3, 3, t]." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3167.
Full textAbstract:
Neste trabalho, nós investigamos sob quais condições um grafo Km,n pertenceá classe ORTH[3, 3, t] introduzida por [Jamison and Mulder 2000]. Mostramos que K4,4 2 / ORTH[3, 3, 4], corroborando uma conjectura de Jamison e Mulder em [Jamison and Mulder 2005]. O principal resultado deste trabalho é a prova da existência de um grafo G ✓ Kn,n e G 2 ORTH[3, 3, 2n 3], se n é uma potência de 2 e n 4.
6
Araújo, J., and P. Arraes. "Número de envoltória em classes de grafos orientados⇤." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3150.
Full textAbstract:
Neste trabalho estudamos o número de envoltória para algumas classes de grafos orientados. Primeiramente apresentamos um limitante superior para o número de envoltória restrito a torneios, além de um torneio para o qual atingimos esse limite. Em seguida provamos que esse problema é NPcompleto para grafos bipartidos orientados. Para tanto utilizamos o resultado de [Araujo et al. 2013], o qual afirma que tal problema é NP-completo para grafos bipartidos não-orientados. Depois mostramos uma caraterização para o menor conjunto de envoltória de umaárvore orientada. Além disso, generalizamos esse resultado ao mostrar um algoritmo de tempo polinomial para calcular o número de envoltória de qualquer grafo cacto orientado.
7
O. Netto, João, and Hebert Silva. "Alocação de salas usando fluxo máximo de custo mínimo em grafos bipartidos." In Escola Regional de Informática de Goiás. Sociedade Brasileira de Computação, 2020. http://dx.doi.org/10.5753/erigo.2020.13867.
Full textAbstract:
Este artigo apresenta uma solução para o problema de alocação de salas no âmbito da UFG. O problema consiste em, dado um conjunto de pedidos para uso de salas e um conjunto de salas disponíveis, otimizar a ocupação das salas garantindo que cada sala tenha capacidade suficiente para que as pessoas fiquem sentadas. Com o aumento de cursos de graduação e pós-graduação e por conseguinte de disciplinas nos campus da UFG, alocar as disciplinas em salas tem se tornando um desafio e consumindo muito tempo pois é feito de forma manual. Este artigo oferece uma solução para o problema usando fluxo máximo de custo mínimo em grafos bipartidos e analisa a alocação atual versus a alocação feita pelo algoritmo, provendo uma alternativa para a alocação manual.
8
Fernandes, Hugo Guércio, and Victor Ströele. "Desenvolvimento de um Modelo Semântico para Recomendação Baseado em Grafos." In Brazilian Workshop on Social Network Analysis and Mining. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/brasnam.2016.6447.
Full textAbstract:
Os sistemas de recomendação têm como objetivo auxiliar um usuário, ou grupos de usuários, na identificação de diferentes itens relevantes às suas necessidades. Com a crescente quantidade de dados, os sistemas de recomendação estão sendo muito estudados, pois é cada vez mais difícil encontrar a informação desejada devido à grande quantidade de alternativas disponíveis. Neste trabalho é proposto e desenvolvido um modelo para um sistema de recomendações baseado em grafos bipartidos, composto por informações semânticas de usuários e itens. Este modelo de recomendação foi avaliado com base em duas provas de conceitos (PoC).
9
Gama, Simone, Rosiane De Freitas, and Ueverton Souza. "Aspectos de complexidade parametrizada e problemas análogos em problemas de lista coloração de grafos e suas variações." In IV Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/etc.2019.6402.
Full textAbstract:
Lista-coloração é uma generalização do problema clássico de coloração de vértices em grafos. Tal problema possui algumas variações, dentre elas a coloração. Neste trabalho, uma redutibilidade do problema da lista coloração para a coloração e pré-coloração estendida é apresentada, para melhor se prover uma análise da coloração sob o enfoque da complexidade parametrizada, onde a mesma é FPT quando parametrizada pela cobertura de vértices e listas de cores. É apresentada também a prova de corretude de um algoritmo polinomial, dado na literatura, para coloração em grafos bipartidos completos.