Seminário de Teoria da Computação O problema do caminho mínimo não-elementar com restrições de recursos Edna Ayako Hoshino Sexta-feira, 10 de outubro de 2008 Sala 322 16:00hs <------ Obs.: Notem sala Resumo: Discuterei uma variante do clássico problema do caminho mínimo, na qual o custo é substituído por um vetor de recursos que são acumulados ao longo do caminho e possuem restrições em nós intermediários. As restrições são definidas pelo consumo mínimo de recursos em cada aresta do grafo e por intervalos de recursos em cada nó do grafo. Uma vez que o problema é NP-difícil, uma relaxação que permite repetição de vértices ao longo do caminho tem sido estudada e é conhecida por problema do caminho mínimo não-elementar com restrições de recursos (SPPRC). Usualmente, existem restrições adicionais na estrutura do caminho, por exemplo, a proibição $k$-ciclos (ciclos de comprimento menor ou igual a $k$). Apresentarei o algoritmo de programação dinâmica, que se baseia em algoritmos de rotulação e no uso de regras de dominâncias, proposto por Irnich e Villeneuve para resolver o SPPRC com proibição de $k$-ciclos. Referencias: INFORMS JOURNAL ON COMPUTING Vol. 18, No. 3, Summer 2006, pp. 391-406 The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k >= 3. Stefan Irnich, Daniel Villeneuve