DOI: 10.1515/comp-2023-0103 ISSN: 2299-1093

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

Samer Nofal
  • General Computer Science


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 1 k-1
-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.

More from our Archive