Recurrence-based Heuristics for the Hamiltonian Path Inclusion and Exclusion and Exclusion Algorithm
Eric T. Bax · CaltechAUTHORS (California Institute of Technology) · 1994
For many problem instances, the inclusion and exclusion formula has many cancellations and symmetries. By imposing a hierarchy on the formula's terms, we develop general reductions for inclusion and exclusion algorithms. We apply these reductions to an algorithm which counts Hamiltonian paths, and we develop a branch and bound algorithm to detect Hamiltonian paths. Then we show how to apply the reductions to other inclusion and exclusion algorithms.