On the Optimal Solutions to AND/OR Series-Parallel Graphs
- 1 July 1971
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 18 (3) , 354-372
- https://doi.org/10.1145/321650.321653
Abstract
[[abstract]]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.[[fileno]]2030256010059[[department]]資訊工程學This publication has 5 references indexed in Scilit:
- Experiments With Some Programs That Search Game TreesJournal of the ACM, 1969
- A Formal Basis for the Heuristic Determination of Minimum Cost PathsIEEE Transactions on Systems Science and Cybernetics, 1968
- Experiments With a Multipurpose, Theorem-Proving Heuristic ProgramJournal of the ACM, 1968
- Branch-and-Bound Methods: A SurveyOperations Research, 1966
- Series-parallel graphs and latticesDuke Mathematical Journal, 1959