A matheuristic approach for solving the 2-connected dominating set problem
<p dir="ltr">This paper describes a matheuristic approach for solving the 2-connected dominating set problem (2-CDS). The goal of the proposed method is to find near optimal solutions for large graphs. The algorithm is based on a Greedy Randomized Adaptive Search Procedure (GRASP). I...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2019
|
| Subjects: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513505608073216 |
|---|---|
| author | Raka Jovanovic (17947838) |
| author2 | Stefan Voß (6943367) |
| author2_role | author |
| author_facet | Raka Jovanovic (17947838) Stefan Voß (6943367) |
| author_role | author |
| dc.creator.none.fl_str_mv | Raka Jovanovic (17947838) Stefan Voß (6943367) |
| dc.date.none.fl_str_mv | 2019-02-27T15:00:00Z |
| dc.identifier.none.fl_str_mv | 10.2298/aadm190227052j |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/A_matheuristic_approach_for_solving_the_2-connected_dominating_set_problem/27021346 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Mathematical sciences Applied mathematics Matheuristic Dominating Set Problem GRASP |
| dc.title.none.fl_str_mv | A matheuristic approach for solving the 2-connected dominating set problem |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <p dir="ltr">This paper describes a matheuristic approach for solving the 2-connected dominating set problem (2-CDS). The goal of the proposed method is to find near optimal solutions for large graphs. The algorithm is based on a Greedy Randomized Adaptive Search Procedure (GRASP). Its performance is enhanced by combining it with a second local search method that uses a Mixed Integer Program. The performance of the proposed method is evaluated on large unit disc graphs having varying edge densities and on general graphs.</p><h2>Other Information</h2><p dir="ltr">Published in: Applicable Analysis and Discrete Mathematics<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.2298/aadm190227052j" target="_blank">https://dx.doi.org/10.2298/aadm190227052j</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_533290be3030e693bd04825620d69e58 |
| identifier_str_mv | 10.2298/aadm190227052j |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/27021346 |
| publishDate | 2019 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | A matheuristic approach for solving the 2-connected dominating set problemRaka Jovanovic (17947838)Stefan Voß (6943367)Mathematical sciencesApplied mathematicsMatheuristicDominating Set ProblemGRASP<p dir="ltr">This paper describes a matheuristic approach for solving the 2-connected dominating set problem (2-CDS). The goal of the proposed method is to find near optimal solutions for large graphs. The algorithm is based on a Greedy Randomized Adaptive Search Procedure (GRASP). Its performance is enhanced by combining it with a second local search method that uses a Mixed Integer Program. The performance of the proposed method is evaluated on large unit disc graphs having varying edge densities and on general graphs.</p><h2>Other Information</h2><p dir="ltr">Published in: Applicable Analysis and Discrete Mathematics<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.2298/aadm190227052j" target="_blank">https://dx.doi.org/10.2298/aadm190227052j</a></p>2019-02-27T15:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.2298/aadm190227052jhttps://figshare.com/articles/journal_contribution/A_matheuristic_approach_for_solving_the_2-connected_dominating_set_problem/27021346CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/270213462019-02-27T15:00:00Z |
| spellingShingle | A matheuristic approach for solving the 2-connected dominating set problem Raka Jovanovic (17947838) Mathematical sciences Applied mathematics Matheuristic Dominating Set Problem GRASP |
| status_str | publishedVersion |
| title | A matheuristic approach for solving the 2-connected dominating set problem |
| title_full | A matheuristic approach for solving the 2-connected dominating set problem |
| title_fullStr | A matheuristic approach for solving the 2-connected dominating set problem |
| title_full_unstemmed | A matheuristic approach for solving the 2-connected dominating set problem |
| title_short | A matheuristic approach for solving the 2-connected dominating set problem |
| title_sort | A matheuristic approach for solving the 2-connected dominating set problem |
| topic | Mathematical sciences Applied mathematics Matheuristic Dominating Set Problem GRASP |