Generalized Longest Path Problems

Authors

  • Gal Dahan Ben-Gurion University of the Negev
  • Itay Tabib Ben-Gurion University of the Negev
  • Eyal Solomon Shimony Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev

Keywords:

Combinatorial Optimization, Problem Solving Using Search

Abstract

The longest simple path and snake-in-a-box are combinatorial search problems of considerable research interest. We create a common framework of longest constrained path in a graph that contains these two problems, as well as other interesting maximum path problems, as special cases. We analyze properties of this general framework, produce bounds on the path length that can be used as admissible heuristics for all problem types therein. For the special cases of longest simple path and snakes, these heuristics are shown to reduce the number of expansions when searching for a maximal path, which in some cases leads to reduced search time despite the significant overhead of computing these heuristics.

Downloads

Published

2022-07-17