The Complexity of Node Counting on Undirected Graphs

The Complexity of Node Counting on Undirected Graphs Boleslaw Szymanski Sven Koenig We analyze the complexity of Node Counting, a graph-traversalmethod. On many graphs arising in control problems in Artificial Intelligence, Node Counting performs as efficiently as othermethodswhich are known to be of polynomial complexity in the number of states (e.g., Learning Real-Time A* method). Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-98-02

The Complexity of Node Counting on Undirected Graphs

Boleslaw Szymanski

Sven Koenig

We analyze the complexity of Node Counting, a graph-traversalmethod. On many graphs arising in control problems in Artificial Intelligence, Node Counting performs as efficiently as othermethodswhich are known to be of polynomial complexity in the number of states (e.g., Learning Real-Time A* method).

Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY

cs-98-02