---
title: "Sparse-Memory Graph Search"
authors:
  - "Rong Zhou"
  - "Eric A. Hansen"
doi: ""
url: "https://ijcai.org/proceedings/2003/179"
pdf: "https://ijcai.org/proceedings/2003/0179.pdf"
venue: "Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence"
year: 2003
pages: "1259-1267"
track: ""
keywords:
---

# Sparse-Memory Graph Search

Rong Zhou, Eric A. Hansen

*Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence*, pages 1259-1267.

## Abstract

We describe a framework for reducing the space complexity of graph search algorithms such as A* that use Open and Closed lists to keep track of the frontier and interior nodes of the search space. We propose a sparse representation of the Closed list in which only a fraction of already expanded nodes need to be stored to perform the two functions of the Closed List- preventing duplicate search effort and allowing solution extraction. Our proposal is related to earlier work on search algorithms that do not use a Closed list at all [Korf and Zhang, 2000]. However, the approach we describe has several advantages that make it effective for a wider variety of problems.