An approach for the Steiner problem in directed graphs |
| |
| Authors: | Nelson Maculan Paulo Souza Alfredo Candia Vejar |
| |
| Affiliation: | (1) COPPE and Institute of Mathematics, Federal University of Rio de Janeiro, P.O. Box 68501, 21945 Rio de Janeiro, Brazil;(2) COPPE-Rio de Janeiro and Departamento de Matemática, Universidad de Tarapacá, Arica, Chile |
| |
| Abstract: | We present a scheme to solve the Steiner problem in directed graphs using a heuristic method to obtain upper bounds and thek shortest arborescences algorithm to compute lower bounds. We propose to combine these ideas in an enumerative algorithm. Computational results are presented for both thek shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.This work was partially supported by CNPq, FINEP, CAPES and IBM do Brasil. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
