Transit Nodes – Lower Bounds and Refined Construction
Jochen Eisner, Stefan Funke · Society for Industrial and Applied Mathematics eBooks · 2012
We reconsider the concept of transit nodes as introduced by Bast et al. [3] and for the first time construct instance based lower bounds on the size of transit node sets by interpreting a LP formulation of the problem and its dual. As a side product we achieve considerably smaller access node sets which directly influences the query time for non-local queries.