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 k−1k-1-vertex subsets are already constructed, our algorithm produces the kk-vertex subsets building on the k−1k-1-vertex subsets rather than reconstructing the kk-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.

Keywords

• discrete optimization
• algorithm
• undirected graph
• toll sets