PORTUGALIAEMATHEMATICA
Vol. 52, No. 4, pp. 475-480 (1995)
|
|
PORTUGALIAE MATHEMATICA Vol. 52, No. 4, pp. 475-480 (1995) |
|
|
When is a 0-1 Knapsack a Matroid?J. Orestes Cerdeira and Paulo BarciaDepartamento de Matemática, Instituto Superior de Agronomia,Tapada da Ajuda, 1399 Lisboa Codex - PORTUGAL E-mail: orestes@isa.utl.pt Universidade Nova de Lisboa, Faculdade de Economia, Travessa Estev\ ao Pinto, Campolide, 1000 Lisboa - PORTUGAL E-mail: barcia@fe.unl.pt Abstract: We give a polynomial time algorithm for deciding whether the set of solutions of a 0-1 knapsack is a matroid. Keywords: 0-1 knapsack; matroids; subset sum problem. Full text of the article:
Electronic version published on: 29 Mar 2001. This page was last modified: 27 Nov 2007.
© 1995 Sociedade Portuguesa de Matemática
|