A hybrid graph representation for recursive backtracking algorithms
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 d...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | conferenceObject |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/10725/5400 http://dx.doi.org/10.1007/978-3-642-14553-7_15 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-642-14553-7_15 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513465867042816 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Langston, Micheal A. Mouawad, Amer E. Nolan, Clinton P. |
| author2_role | author author author |
| author_facet | Abu-Khzam, Faisal N. Langston, Micheal A. Mouawad, Amer E. Nolan, Clinton P. |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Langston, Micheal A. Mouawad, Amer E. Nolan, Clinton P. |
| dc.date.none.fl_str_mv | 2017-03-20T08:25:46Z 2017-03-20T08:25:46Z 2017-03-20 |
| dc.identifier.none.fl_str_mv | 978-3-642-14553-7 http://hdl.handle.net/10725/5400 http://dx.doi.org/10.1007/978-3-642-14553-7_15 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. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-642-14553-7_15 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Springer |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | A hybrid graph representation for recursive backtracking algorithms Frontiers in Algorithmics |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_f2ecbaa79517855e7a3519212f8ea096 |
| identifier_str_mv | 978-3-642-14553-7 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. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/5400 |
| publishDate | 2017 |
| publisher.none.fl_str_mv | Springer |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | A hybrid graph representation for recursive backtracking algorithmsFrontiers in AlgorithmicsAbu-Khzam, Faisal N.Langston, Micheal A.Mouawad, Amer E.Nolan, Clinton P.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.N/ASpringer2017-03-20T08:25:46Z2017-03-20T08:25:46Z2017-03-20Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObject978-3-642-14553-7http://hdl.handle.net/10725/5400http://dx.doi.org/10.1007/978-3-642-14553-7_15Abu-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.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://link.springer.com/chapter/10.1007/978-3-642-14553-7_15eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/54002021-03-19T10:00:51Z |
| spellingShingle | A hybrid graph representation for recursive backtracking algorithms Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | A hybrid graph representation for recursive backtracking algorithms |
| title_full | A hybrid graph representation for recursive backtracking algorithms |
| title_fullStr | A hybrid graph representation for recursive backtracking algorithms |
| title_full_unstemmed | A hybrid graph representation for recursive backtracking algorithms |
| title_short | A hybrid graph representation for recursive backtracking algorithms |
| title_sort | A hybrid graph representation for recursive backtracking algorithms |
| url | http://hdl.handle.net/10725/5400 http://dx.doi.org/10.1007/978-3-642-14553-7_15 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-642-14553-7_15 |