A hybrid graph representation for recursive backtracking algorithms

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Langston, Micheal A.
dc.contributor.author Mouawad, Amer E.
dc.contributor.author Nolan, Clinton P.
dc.date.accessioned 2017-03-20T08:25:46Z
dc.date.available 2017-03-20T08:25:46Z
dc.identifier.isbn 978-3-642-14553-7 en_US
dc.identifier.uri http://hdl.handle.net/10725/5400
dc.description.abstract Many exact algorithms for NPNP -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 O(1)O(1) adjacency-queries in adjacency-matrices with the advantage of efficient neighborhood traversal in adjacency-lists. en_US
dc.language.iso en en_US
dc.publisher Springer en_US
dc.title A hybrid graph representation for recursive backtracking algorithms en_US
dc.type Conference Paper / Proceeding en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.keywords Data structures en_US
dc.keywords Exact algorithms en_US
dc.keywords Recursive backtracking en_US
dc.keywords Vertex cover en_US
dc.keywords Dominating set en_US
dc.identifier.doi http://dx.doi.org/10.1007/978-3-642-14553-7_15 en_US
dc.identifier.ctation Abu-Khzam, F. N., Langston, M. A., Mouawad, A. E., & Nolan, C. P. (2010, August). A hybrid graph representation for recursive backtracking algorithms. In International Workshop on Frontiers in Algorithmics (pp. 136-147). Springer Berlin Heidelberg. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.date August 11-13, 2010 en_US
dc.conference.pages 136-147 en_US
dc.conference.place Wuhan, China en_US
dc.conference.title 4th International Workshop on Frontiers in Algorithmics en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://link.springer.com/chapter/10.1007/978-3-642-14553-7_15 en_US
dc.author.affiliation Lebanese American University en_US
dc.title.volume Frontiers in Algorithmics en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account