On the Optimal Solutions to AND/OR Series-Parallel Graphs

This paper is concerned with efficient ways to find optimal solutions to AND/OR graphs. Although the general methods are still at large, we have found an efficient way to obtain optimal solutions to AND/OR series-parallel graphs. This is achieved by reducing an AND/OR series-parallel graph to an AND/OR tree. Once a graph is reduced to a tree, all the known exact and heuristic methods of tree searching can be applied.