Duplicate Avoidance in Depth-First Search with Applications to Treewidth
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 480-484.
Abstract
Depth-first search is effective at solving hard combinatorial problems, but if the problem space has a graph structure the same nodes may be searched many times. This can increase the size of the search exponentially. We explore two techniques that prevent this: duplicate detection and duplicate avoidance. We illustrate these techniques on the treewidth problem, a combinatorial optimization problem with applications to a variety of research areas. The bottleneck for previous treewidth algorithms is a large memory requirement. We develop a duplicate avoidance technique for treewidth and demonstrate that it significantly outperforms other algorithms when memory is limited. Additionally, we are able to find, for the first time, the treewidth of several hard benchmark graphs.P. Alex Dow, Richard E. Korf
@inproceedings{ijcai2009p87,
title = {Duplicate Avoidance in Depth-First Search with Applications to Treewidth},
author = {Dow, P. Alex and Korf, Richard E.},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {480--484},
year = {2009},
url = {https://ijcai.org/proceedings/2009/87},
}
TY - CPAPER TI - Duplicate Avoidance in Depth-First Search with Applications to Treewidth AU - Dow, P. Alex AU - Korf, Richard E. T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 480 EP - 484 UR - https://ijcai.org/proceedings/2009/87 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
