VIANA, Luiz Alberto do Carmo. Árvore geradora com dependências mínima. 2016. 69 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-09-09T12:32:49Z
No. of bitstreams: 1
2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2016-09-27T17:45:27Z (GMT) No. of bitstreams: 1
2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5) / Made available in DSpace on 2016-09-27T17:45:27Z (GMT). No. of bitstreams: 1
2016_dis_lacviana.pdf: 590271 bytes, checksum: 9bf849e4e918431886cbd4c9beca22b3 (MD5)
Previous issue date: 2016 / We introduce the Dependency Constrained Minimum Spanning Tree Problem, DCMST(G,D,w), defined over a graph G(V,E) and a digraph D(E,A), whose vertices are the edges of G and whose arcs describe dependency relations between these edges. Such problem consists of finding, among the spanning trees of G(V,E) satisfying the dependency constraints imposed by D(E,A), that one whose cost is minimum, according to a edgeweight function w. The dependency constraints impose that an edge e of G can be part of a solution either if it is a source in D or if some other edge e′, such that the arc (e′, e) is in D, is part of it as well. We prove that deciding whether there is a feasible solution to DCMST(G,D,w) is an NP-complete problem, even if G is a chordal cactus and D is a union of arborescences of height at most 2. NP-completeness also applies if G is bipartite, the dependency constraints occur only between adjacent edges of G and their related arcs describe arborescences whose height is at most 2. The same results are obtained for the problem variants which demand that, instead of “some”, “exactly one”or “all”dependencies be part of a solution. To solve the problem, we introduce some integer programming formulations and some valid inequalities. We propose a strategy to reduce the problem dimension by excluding some edges of G according to the structure of D. We evaluate the introduced models and algorithms using randomly generated instances. Computational results are reported. / Introduzimos o problema de Árvore Geradora com Dependências Mínima, AGDM(G,D,w), definido sobre um grafo G(V,E) e um digrafo D(E,A), cujos vértices são as arestas de G e cujos arcos definem dependências entre tais arestas. O problema consiste em encontrar, dentre as árvores geradoras do grafo G(V,E) que satisfaçam as restrições de dependência impostas pelo digrafo de entrada D(E,A), uma que tenha custo mínimo, segundo a ponderação w das arestas de G. As restrições de dependência exigem que uma aresta e de G só pode fazer parte de uma solução se for uma fonte em D ou se fizer parte da solução alguma outra aresta é tal que o arco (e′, e) esteja em D. Provamos que decidir se há solução viável para AGDM(G,D,w) é um problema NP-completo, mesmo quando G é um cacto cordal e D é a união de arborescências de altura no máximo 2. Sua NP-completude também é mostrada ainda que G seja bipartido, as restrições de dependência ocorram apenas entre arestas adjacentes de G e formem arborescências de altura no máximo 2. Resultados idênticos são obtidos para as variantes do problema onde, nas restrições de dependência, substitui-se o requisito “alguma” por “exatamente uma” ou “toda”. Para resolver o problema, apresentamos algumas formulações de programação inteira e desigualdades válidas. Propomos uma estratégia para reduzir a dimensão do problema, excluindo arestas de G com base na estrutura de D. Avaliamos os modelos e algoritmos propostos usando instâncias geradas aleatoriamente. Resultados computacionais são reportados.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.repositorio.ufc.br:riufc/19793 |
| Date | January 2016 |
| Creators | Viana, Luiz Alberto do Carmo |
| Contributors | Campelo Neto, Manoel Bezerra |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds