On the Optimal Solutions to AND/OR Series-Parallel Graphs
Richard Simon, Richard C. T. Lee · Journal of the ACM · 1971
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.