Use este identificador para citar ou linkar para este item:
http://repositorio.ufc.br/handle/riufc/46915| Tipo: | Dissertação |
| Título: | Um estudo de redes com fluxos ramificados arco-disjuntos |
| Título em inglês: | A study of networks with arc-disjoint branching flows |
| Autor(es): | Silva, Jonas Costa Ferreira da |
| Orientador: | Oliveira, Ana Karolinna Maia de |
| Coorientador: | Sales, Cláudia Linhares |
| Palavras-chave: | Fluxos arco-disjuntos;Fluxo em rede;Digrafos;Teoria dos grafos |
| Data do documento: | 2019 |
| Citação: | SILVA, Jonas Costa Ferreira da. Um estudo de redes com fluxos ramificados arco-disjuntos. 2019. 51 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal do Ceará, Fortaleza, 2019. |
| Resumo: | Redes e fluxos são utilizados na modelagem de problemas de diversos domínios como: roteamento, circuitos elétricos, redes de computadores até a generalização de problemas de caminhos em digrafos. No conceito de fluxos arco-disjuntos, introduzido por (BANG-JENSEN; BESSY, 2014), não estamos interessados apenas em encontrar um fluxo viável em uma rede, mas sim múltiplos fluxos viáveis que sejam arco-disjuntos entre si. Essa generalização permitiu a modelagem de novos problemas utilizando os conceitos familiares de fluxo, desde problemas polinomiais, como aquele de decidir se um multigrafo direcionado possui k ramificações arco-disjuntas, a problemas N P-completos, como o problema de decidir sobre a existência de caminhos arco-disjuntos entre vértices pré-determinados. Neste trabalho, realizamos um estudo sobre fluxos arco-disjuntos com enfoque em fluxos ramificados, que são fluxos que possuem um vértice fonte que envia fluxo para todos os demais vértices, de modo que cada um dos demais retenha uma unidade de fluxo. Tendo como parâmetro a função de capacidade da rede, estudamos também a complexidade do problema de encontrar fluxos ramificados arco-disjuntos. A partir de resultados de (EDMONDS, 1973) e (BANGJENSEN et al., 2016), propomos uma conjectura que caracteriza (ainda com base na função de capacidade) as redes que possuem múltiplos fluxos ramificados arco-disjuntos e mostramos alguns casos em que ela é válida. |
| Abstract: | Network flows constitute a very useful tool for modeling problems of different areas such as: routing, electrical circuits, computer networks and even path problems on digraphs. The arc-disjoint flows problem was introduced by (BANG-JENSEN; BESSY, 2014) and it is a generalization of the classical flow problem in which we are interested in deciding whether a network admits multiple arc-disjoint feasible flows. On this generalized version, is possible to model new problems using flow tools, from polynomial ones, such as the problem of finding multiple arc-disjoint out-branchings, to N P-complete ones, such as the problem of deciding whether exists arc-disjoint paths between prescribed pairs of vertices. In this work, we study the arc-disjoint flow problem with focus on branching flows, which are flows where a vertex sends a unit of flow to all the other vertices. Considering the network capacity function as parameter we studied the complexity of finding two arc-disjoint branching flows. Based on results of (EDMONDS, 1973) and (BANG-JENSEN et al., 2016) we proposed a conjecture to characterize (also based on the capacity function) the networks which admit multiple arc-disjoint branching flows and we also showed some cases where it holds. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/46915 |
| Aparece nas coleções: | DCOMP - Dissertações defendidas na UFC |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 2019_dis_jcfsilva.pdf | 657,54 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.