Graph theoretic algorithms for the PLA folding problem

Graph theoretic properties of the PLA folding problem which not only give insight into the various folding problems but also provide efficient algorithms for solving the problems are presented. This work is based on the transformation of the PLA into graphs where cliques (completely connected subgraphs) in the graphs correspond to PLA folding sets. A simple heuristic technique known as the greedy algorithm can often identify near-maximum cliques in polynomial time. Experimental data show that this technique is extremely effective when applied to the graphs which generally arise in folding. Variations of the general folding problem such as bipartite folding and constrained folding are addressed