ISSN:
1572-9338
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract The concept ofimage of an integrally weighted combinatorial problem is introduced as the vector of all possible weights of feasible solutions. This preliminary work begins to explore the possible applications of this concept and to study the computational complexity of image computations. It is shown that the images of spanning trees, matroid bases, perfect matchings and, more generally, matroid parity bases can be computed in polynomial time for some "bottleneck" objective functions (such as, for instance, the maximum weight of an element), whereas (random) pseudo-polynomial time is needed when the objective function is the sum of the element weights.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02115754
Permalink