Árvore geradora com dependências mínima

Detalhes bibliográficos
Ano de defesa: 2016
Autor(a) principal: Viana, Luiz Alberto do Carmo
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/19793
Resumo: 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.