The Generalized Cardinality Constrained Shortest Path Problem (GCCSPP) consists in finding the minimum cost path in a digraph, using at most r arcs in a subset F of the arc set. We propose an algebraic chacracterization of the extreme points of the associated polytope, and then we show that it is equivalent to the geometric one, obtained extendeing to the GCCSPP some known results for the Cardinality Constrained Shortest Path Problem.
Some observations about the extreme points of the Generalized Cardinality-Constrained Shortest Path Problem polytope
MONACO, Maria Flavia;
2008-01-01
Abstract
The Generalized Cardinality Constrained Shortest Path Problem (GCCSPP) consists in finding the minimum cost path in a digraph, using at most r arcs in a subset F of the arc set. We propose an algebraic chacracterization of the extreme points of the associated polytope, and then we show that it is equivalent to the geometric one, obtained extendeing to the GCCSPP some known results for the Cardinality Constrained Shortest Path Problem.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
