MASCOTTE no longer exists => visit the new project-team
Seminaire MASCOTTERisk Models for Prize Collecting Steiner Tree Problem with Interval Data.
par Bi Li
| Date : | 11/10/11 | | Time : | 10:30 | | Location : | Galois Coriolis |
Ă‚' Given a connected graph G = (V;E) with a nonnegative cost on each edge in E, a nonnegative prize at each vertex in V, the Prize Collecting Steiner Tree (PCST) problem is to nd a tree T in G such that the total cost on edges in T minus the total prize at vertices in T is minimized.
While the problem is NP-hard in general, it is polynomial-time solvable when graphs G are restricted to series-parallel graphs. We also study the PCST problem with interval costs and prizes.
Page des séminaires
| 
