Two Dependency Constrained Spanning Tree Problems
Apresentação
We introduce two spanning tree problems with dependency constraints, where an edge can be chosen only if emph{at least} one or emph{all} edges in its dependency set are also chosen, respectively. The dependencies on the input graph $G$ are described by a digraph $D$ whose vertices are the edges of $G$, and the in-neighbors of a vertex are its dependency set. We show that both problems are NP-hard even if $G$ is a chordal cactus with diameter 2 or maximum degree 3, and $D$ is a disjoint union of arborescences of height 2. We also prove that the problems are inapproximable to a $ln n$ factor, unless $P=NP,$ and that they are $W[2]$-hard. On the other hand, we present some polynomial cases. We test ILP formulations based on DCUT and MTZ constraints. Computational experiments are reported.
Programação
Palestra: "Two Dependency Constrained Spanning Tree Problems"
- Luiz Alberto do Carmo Viana
- Sala 04
- 02 horas
-
.png)
21/08 a 10/11/2023
Encontros Universitários 2023
-
24/08 a 18/12/2023
Monitoria 2023.2 - Fisíca Geral II
-
24/08 a 18/12/2023
Monitoria 2023.2 - Arquitetura de Computadores
-
25/10 a 26/10/2023
5ª Semana do Livro e da Biblioteca