Título:** ****The Generalized Dependency Constrained Spanning Tree Problem**

Data: **30/09/2019**

Horário: **10:00****h**

Local: **Sala de Seminários - Bloco 952**

Resumo:

We introduce the Generalized Dependency Constrained Spanning Tree Problem (G-DCST), where an edge can be chosen only if the number of edges chosen from its dependency set lies in a certain interval. The dependency relations between the edges of the input graph G are described by the input digraph D, whose vertices are the edges of G. The in-neighbors of a vertex of D form its dependency set. We show that G-DCST unifies and generalizes some known spanning tree problems that apply conflict constraints over edges or lower and upper bounds on vertex degrees. We show that the feasibility version of G-DCST is NP-complete even under strong restrictions on the structures of G and D as well as on the functions that define the minimum or maximum number of dependencies to be satisfied. We also show that this problem keeps an ln n inapproximability threshold under tight assumptions over G and D. On the other hand, we spot a polynomial case via a matroid intersection argument.

Banca:

- Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC - Orientador)
- Prof. Dra. Claudia Linhares Sales (MDCC/UFC)
- Prof. Dra. Ana Shirley Ferreira da Silva (UFC)

Última atualização (Sex, 27 de Setembro de 2019 14:54)