| |
|
Description: |
Neste seminário serão analisadas algumas formulações conhecidas para o problema da determinação de uma árvore de suporte de custo minimo sobre um grafo, com uma restrição adicional que limita superiormente o número de nodos em cada subárvore incidente num determinado nodo desse grafo, designado por raiz. Esta restrição adicional coloca este problema na classe dos NP-Difíceis, para determinados valores da capacidade. Procurar-se-á fazer uma breve revisão dessas formulações, que passam por modelos naturais, estendidos, orientados e não orientados, a partir dos quais vários autores determinaram limites inferiores para o custo da solução óptima do problema, recorrendo a técnicas conhecidas: técnicas de decomposição, relaxação linear e algoritmos de planos de corte. Apontar-se-ão vantagens e desvantagens entre as várias formulações, com base em alguns resultados computacionais.
Area(s):
|
|
Date: |
|
| Start Time: |
11:00 |
|
Speaker: |
Pedro Coimbra Martins (ISCAC, Portugal)
|
|
Place: |
Room 5.7
|
| Research Groups: |
-Numerical Analysis and Optimization
|
|
See more:
|
<Main>
|
|
