Modular-width
Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. propo...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| التنسيق: | conferenceObject |
| منشور في: |
2017
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/7490 http://dx.doi.org/10.1007/978-3-319-59605-1 13 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-59605-1_13 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513482162962432 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Markarian, Christine Podipyan, Pavel |
| author2_role | author author |
| author_facet | Abu-Khzam, Faisal N. Markarian, Christine Podipyan, Pavel |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Markarian, Christine Podipyan, Pavel |
| dc.date.none.fl_str_mv | 2017 2018-04-23T12:46:32Z 2018-04-23T12:46:32Z 2018-04-23 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7490 http://dx.doi.org/10.1007/978-3-319-59605-1 13 Abu-Khzam, F. N., Li, S., Markarian, C., auf der Heide, F. M., & Podlipyan, P. (2017, June). Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity. In International Workshop on Frontiers in Algorithmics (pp. 139-150). Springer, Cham. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-59605-1_13 |
| 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 | Modular-width an auxiliary parameter for parameterized parallel complexity Frontiers in Algorithmics |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | Many graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_ef68a3960de6ec6f142adcd48d540a2e |
| identifier_str_mv | Abu-Khzam, F. N., Li, S., Markarian, C., auf der Heide, F. M., & Podlipyan, P. (2017, June). Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity. In International Workshop on Frontiers in Algorithmics (pp. 139-150). 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/7490 |
| publishDate | 2017 |
| publisher.none.fl_str_mv | Springer |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Modular-widthan auxiliary parameter for parameterized parallel complexityFrontiers in AlgorithmicsAbu-Khzam, Faisal N.Markarian, ChristinePodipyan, PavelMany graph problems such as maximum cut, chromatic number, hamiltonian cycle, and edge dominating set are known to be fixed-parameter tractable (FPT) when parameterized by the treewidth of the input graphs, but become W-hard with respect to the clique-width parameter. Recently, Gajarský et al. proposed a new parameter called modular-width using the notion of modular decomposition of graphs. They showed that the chromatic number problem and the partitioning into paths problem, and hence hamiltonian path and hamiltonian cycle, are FPT when parameterized by this parameter. In this paper, we study modular-width in parameterized parallel complexity and show that the weighted maximum clique problem and the maximum matching problem are fixed-parameter parallel-tractable (FPPT) when parameterized by this parameter.N/ASpringer2018-04-23T12:46:32Z2018-04-23T12:46:32Z20172018-04-23Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObjecthttp://hdl.handle.net/10725/7490http://dx.doi.org/10.1007/978-3-319-59605-1 13Abu-Khzam, F. N., Li, S., Markarian, C., auf der Heide, F. M., & Podlipyan, P. (2017, June). Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity. In International Workshop on Frontiers in Algorithmics (pp. 139-150). Springer, Cham.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://link.springer.com/chapter/10.1007/978-3-319-59605-1_13eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/74902021-03-19T10:43:20Z |
| spellingShingle | Modular-width Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | Modular-width |
| title_full | Modular-width |
| title_fullStr | Modular-width |
| title_full_unstemmed | Modular-width |
| title_short | Modular-width |
| title_sort | Modular-width |
| url | http://hdl.handle.net/10725/7490 http://dx.doi.org/10.1007/978-3-319-59605-1 13 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-59605-1_13 |