A combinatorial algorithm and its application in computing all minimum toll sets of graphs

Abstract

This article formalizes an algorithm that computes the minimum toll sets in an undirected graph. A core process in our algorithm is to check vertex subsets in order of size. We add a new flavor to the implementation of this process; when the

-vertex subsets are already constructed, our algorithm produces the

k k

-vertex subsets building on the

k − 1 k-1

-vertex subsets rather than reconstructing the

k k

-vertex subsets from the ground up as the existing algorithms would do. Our implementation is usable in combinatorial minimization problems that require checking variable-size combinations in order of size.