An efficient algorithm for searching implicit AND/OR graphs with cycles
We present an efficient \(AO^{*}\)-like algorithm that handles cyclic graphs without neither unfolding the cycles nor looping through them. Its top-down search strategy is based on Mahanti and Bagchi's CF [\textit{A. Mahanti} and \textit{A. Bagchi}, J. Assoc. Comput. Math. 32, 28-51 (1985; Zbl 0633.68098)], whereas its bottom-up revision process is inspired in Chakrabarti's \(\text{REV}^{*}\) [\textit{P. P. Chakrabarti}, Artif. Intell. 65, No. 2, 329-345 (1994; Zbl 0803.68123)]. However, important modifications have been introduced in both algorithms to attain a true integration and gain efficiency. Proofs of correctness and completeness are included. Up to our knowledge, the resulting algorithm -- called \(CFC_{REV^{*}}\) -- is the most efficient one available for this problem.
- scientific article; zbMATH DE number 1247175
- The complexity of searching implicit graphs
- An efficient approximation algorithm for counting \(n\)-cycles in a graph
- Efficient Deterministic Algorithms for Finding a Minimum Cycle Basis in Undirected Graphs
- Effective search for all maximal mean cycles in a graph
- scientific article; zbMATH DE number 1538872
- Searching Cycle-Disjoint Graphs
- Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
- Efficient approximation algorithms for shortest cycles in undirected graphs
- High Performance Computing - HiPC 2003
- A general heuristic bottom-up procedure for searching AND/OR graphs
- Admissibility of \(AO^ *\) when heuristics overestimate
- Admissible heuristic search in AND/OR graphs
- Algorithms for searching explicit AND/OR graphs and their applications to problem reduction search
- An admissible and optimal algorithm for searching AND/OR graphs
- An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems
- AND/OR graph heuristic search methods
- Best First Search Algorithm in AND/OR Graphs with Cycles
- scientific article; zbMATH DE number 3657150 (Why is no real title available?)
- Intractability of assembly sequencing: unit disks in the plane
- Optimizing decision trees through heuristically guided search
- Improving the efficiency of depth-first search by cycle elimination
- Algorithms for searching explicit AND/OR graphs and their applications to problem reduction search
- Strong planning under partial observability
- State space search nogood learning: online refinement of critical-path dead-end detectors in planning
- Searching for a minimal solution subgraph in explicit AND/OR graphs
- LAO*: A heuristic search algorithm that finds solutions with loops
This page was built for publication: An efficient algorithm for searching implicit AND/OR graphs with cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589573)
