Please use this identifier to cite or link to this item:
http://hdl.handle.net/10773/34906
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Ferreira, António Luis Campos de Sousa | pt_PT |
dc.contributor.author | Martins, Joana Dirce Santos | pt_PT |
dc.date.accessioned | 2022-10-17T14:51:33Z | - |
dc.date.available | 2022-10-17T14:51:33Z | - |
dc.date.issued | 2022-07-22 | - |
dc.identifier.uri | http://hdl.handle.net/10773/34906 | - |
dc.description.abstract | The division of graphs, as abstract descriptions of interacting components of a system, is one of the fundamental operations made on graphs, and it can be done using a great variety of algorithms. This work is focused on the division of a graph into two parts using inference methods. One of them is the Belief Propagation algorithm, known for its small runtime, specially when compared with Monte Carlo based methods. However, despite its success on the estimation of the partitioning cost lower bound in most of the situations, when it comes to determine the graph nodes that belong to each group so that such an optimal cost is obtained, the fast Belief Propagation approach tends to fail. In this context, it was developed a partitioning algorithm based on the Wang-Landau algorithm (a Monte Carlo method), that despite having a longer runtime is often more successful as a problem solver. | pt_PT |
dc.description.abstract | A divisão de grafos, como descrições abstratas de componentes que interagem num sistema, é uma das operações fundamentais em grafos, e pode ser feita usando uma grande variedade de algoritmos. Este trabalho está focado na divisão de um grafo em duas partes usando métodos de inferência. Um deles é o algoritmo de Belief Propagation, especialmente conhecido pelo seu curto tempo de execução, principalmente quando comparado com métodos de Monte Carlo. No entanto, apesar do seu sucesso na estimativa do limite inferior do custo de partição na maioria das situações, quando se trata de determinar os nós do grafo que pertencem a cada grupo de modo a que tal custo ótimo seja obtido, a abordagem rápida da Belief Propagation tende a falhar. Neste contexto, foi desenvolvido um algoritmo de partição baseado no algoritmo de Wang-Landau (um método de Monte Carlo), que apesar de ter um tempo de execução mais longo é frequentemente mais bem sucedido em solucionar problemas concretos. | pt_PT |
dc.language.iso | eng | pt_PT |
dc.rights | openAccess | pt_PT |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | pt_PT |
dc.subject | Graphs | pt_PT |
dc.subject | Factor graphs | pt_PT |
dc.subject | Partitioning | pt_PT |
dc.subject | Wang-Landau method | pt_PT |
dc.subject | Belief propagation algorithm | pt_PT |
dc.title | Monte Carlo Wang-Landau algorithm and belief propagation for graph bipartitioning | pt_PT |
dc.title.alternative | Algoritmo de Monte Carlo Wang-Landau e belief propagation para bipartição de grafos | pt_PT |
dc.type | masterThesis | pt_PT |
thesis.degree.grantor | Universidade de Aveiro | pt_PT |
dc.description.master | Mestrado em Engenharia Computacional | pt_PT |
Appears in Collections: | UA - Dissertações de mestrado DETI - Dissertações de mestrado DFis - Dissertações de mestrado DMat - Dissertações de mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Documento_Joana_Martins.pdf | 1.61 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.