ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems
share
Given a graph G and two independent sets S, T of G, the independent set reconfiguration problem is the problem to determine whether T can be obtained by repleatedly removing and adding a vertex from and to S, while intermediate sets must be also independent. This paper proposes an algorithm for the independent set reconfiguration problem using a data structure, called zero-suppressed binary decision diagrams (ZDDs). This algorithm can be generalized to various reconfiguration problems.
READ FULL TEXT