A hybrid graph representation for exact graph algorithms
Many exact search algorithms for NP-hard graph problems adopt the old Davis-Putman branch-and-reduce paradigm. The performance of these algorithms often suffers from the increasing number of graph modifications, such as vertex/edge deletions, that reduce the problem instance and have to be "tak...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | conferenceObject |
| Published: |
2014
|
| Online Access: | http://hdl.handle.net/10725/7489 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://arxiv.org/abs/1404.6399v1 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Many exact search algorithms for NP-hard graph problems adopt the old Davis-Putman branch-and-reduce paradigm. The performance of these algorithms often suffers from the increasing number of graph modifications, such as vertex/edge deletions, that reduce the problem instance and have to be "taken back" frequently during the search process. We investigate practical implementation-based aspects of exact graph algorithms by providing a simple hybrid graph representation that trades space for time to address the said take-back challenge. Experiments on three well studied problems show consistent significant improvements over classical methods. |
|---|