Advertisement
Published in:
2010 | OriginalPaper | Chapter
A Hybrid Graph Representation for Recursive Backtracking Algorithms
Authors : Faisal N. Abu-Khzam, Michael A. Langston, Amer E. Mouawad, Clinton P. Nolan
Published in: Frontiers in Algorithmics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Many exact algorithms for
$\mathcal{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 deletions, that reduce the problem instance and have to be “taken back” frequently during the search process. The use of efficient data structures is necessary for fast graph modification modules as well as fast take-back procedures. In this paper, we investigate practical implementation-based aspects of exact algorithms by providing a hybrid graph representation that addresses the take-back challenge and combines the advantage of
${\mathcal{O}}(1)$
adjacency-queries in adjacency-matrices with the advantage of efficient neighborhood traversal in adjacency-lists.