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 characterization of the extreme points of the associated polytope, and then we show that it is equivalent to the geometric one, obtained extending 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
Sammarra Marcello;Moccia Luigi
2008
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 characterization of the extreme points of the associated polytope, and then we show that it is equivalent to the geometric one, obtained extending 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.
