On the parameterized parallel complexity and the vertex cover problem
Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , , , |
| التنسيق: | conferenceObject |
| منشور في: |
2016
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/7519 http://dx.doi.org/10.1007/978-3-319-48749-6 35 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007%2F978-3-319-48749-6_35 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513482390503425 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Li, Shouwei Markarian, Chrisitne Meyer auf der Heide, Friedhelm Podipyan, PAvel |
| author2_role | author author author author |
| author_facet | Abu-Khzam, Faisal N. Li, Shouwei Markarian, Chrisitne Meyer auf der Heide, Friedhelm Podipyan, PAvel |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Li, Shouwei Markarian, Chrisitne Meyer auf der Heide, Friedhelm Podipyan, PAvel |
| dc.date.none.fl_str_mv | 2016 2018-04-24T11:52:41Z 2018-04-24T11:52:41Z 2018-04-24 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7519 http://dx.doi.org/10.1007/978-3-319-48749-6 35 Abu-Khzam, F. N., Li, S., Markarian, C., auf der Heide, F. M., & Podlipyan, P. (2016, December). On the parameterized parallel complexity and the vertex cover problem. In International Conference on Combinatorial Optimization and Applications (pp. 477-488). Springer, Cham. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007%2F978-3-319-48749-6_35 |
| 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 | On the parameterized parallel complexity and the vertex cover problem Combinatorial Optimization and Applications |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | Efficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known k-vertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using O(m) instead of O(n2) parallel processors, the running time improves from 4logn+O(kk) to O(k⋅log3n) , where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_b39a34b278e1f339331e3148749ee9aa |
| identifier_str_mv | Abu-Khzam, F. N., Li, S., Markarian, C., auf der Heide, F. M., & Podlipyan, P. (2016, December). On the parameterized parallel complexity and the vertex cover problem. In International Conference on Combinatorial Optimization and Applications (pp. 477-488). Springer, Cham. |
| 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/7519 |
| publishDate | 2016 |
| publisher.none.fl_str_mv | Springer |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | On the parameterized parallel complexity and the vertex cover problemCombinatorial Optimization and ApplicationsAbu-Khzam, Faisal N.Li, ShouweiMarkarian, ChrisitneMeyer auf der Heide, FriedhelmPodipyan, PAvelEfficiently parallelizable parameterized problems have been classified as being either in the class FPP (fixed-parameter parallelizable) or the class PNC (parameterized analog of NC), which contains FPP as a subclass. In this paper, we propose a more restrictive class of parallelizable parameterized problems called fixed-parameter parallel-tractable (FPPT). For a problem to be in FPPT, it should possess an efficient parallel algorithm not only from a theoretical standpoint but in practice as well. The primary distinction between FPPT and FPP is the parallel processor utilization, which is bounded by a polynomial function in the case of FPPT. We initiate the study of FPPT with the well-known k-vertex cover problem. In particular, we present a parallel algorithm that outperforms the best known parallel algorithm for this problem: using O(m) instead of O(n2) parallel processors, the running time improves from 4logn+O(kk) to O(k⋅log3n) , where m is the number of edges, n is the number of vertices of the input graph, and k is an upper bound of the size of the sought vertex cover. We also note that a few P-complete problems fall into FPPT including the monotone circuit value problem (MCV) when the underlying graphs are bounded by a constant Euler genus.N/ASpringer2018-04-24T11:52:41Z2018-04-24T11:52:41Z20162018-04-24Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObjecthttp://hdl.handle.net/10725/7519http://dx.doi.org/10.1007/978-3-319-48749-6 35Abu-Khzam, F. N., Li, S., Markarian, C., auf der Heide, F. M., & Podlipyan, P. (2016, December). On the parameterized parallel complexity and the vertex cover problem. In International Conference on Combinatorial Optimization and Applications (pp. 477-488). Springer, Cham.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://link.springer.com/chapter/10.1007%2F978-3-319-48749-6_35eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/75192021-03-19T10:43:12Z |
| spellingShingle | On the parameterized parallel complexity and the vertex cover problem Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | On the parameterized parallel complexity and the vertex cover problem |
| title_full | On the parameterized parallel complexity and the vertex cover problem |
| title_fullStr | On the parameterized parallel complexity and the vertex cover problem |
| title_full_unstemmed | On the parameterized parallel complexity and the vertex cover problem |
| title_short | On the parameterized parallel complexity and the vertex cover problem |
| title_sort | On the parameterized parallel complexity and the vertex cover problem |
| url | http://hdl.handle.net/10725/7519 http://dx.doi.org/10.1007/978-3-319-48749-6 35 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007%2F978-3-319-48749-6_35 |