Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
F.N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, P. Podlipyan, in: Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW), 2017, pp. 139–150.
Download
Modular-WidthAnAuxiliaryParame.pdf
238.28 KB
Conference Paper
| English
Author
Abu-Khzam, Faisal N.;
Li, Shouwei;
Markarian, ChristineLibreCat;
Meyer auf der Heide, FriedhelmLibreCat;
Podlipyan, Pavel
Abstract
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.
Publishing Year
Proceedings Title
Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)
forms.conference.field.series_title_volume.label
LNCS
Page
139-150
LibreCat-ID
Cite this
Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity. In: Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW). LNCS. ; 2017:139-150. doi:10.1007/978-3-319-59605-1_13
Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., & Podlipyan, P. (2017). Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity. In Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW) (pp. 139–150). https://doi.org/10.1007/978-3-319-59605-1_13
@inproceedings{Abu-Khzam_Li_Markarian_Meyer auf der Heide_Podlipyan_2017, series={LNCS}, title={Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity}, DOI={10.1007/978-3-319-59605-1_13}, booktitle={Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW)}, author={Abu-Khzam, Faisal N. and Li, Shouwei and Markarian, Christine and Meyer auf der Heide, Friedhelm and Podlipyan, Pavel}, year={2017}, pages={139–150}, collection={LNCS} }
Abu-Khzam, Faisal N., Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, and Pavel Podlipyan. “Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity.” In Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW), 139–50. LNCS, 2017. https://doi.org/10.1007/978-3-319-59605-1_13.
F. N. Abu-Khzam, S. Li, C. Markarian, F. Meyer auf der Heide, and P. Podlipyan, “Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity,” in Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW), 2017, pp. 139–150.
Abu-Khzam, Faisal N., et al. “Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity.” Proceedings of the 11th International Workshop on Frontiers in Algorithmics (FAW), 2017, pp. 139–50, doi:10.1007/978-3-319-59605-1_13.
Main File(s)
File Name
Modular-WidthAnAuxiliaryParame.pdf
238.28 KB
Access Level
Closed Access
Last Uploaded
2018-11-02T15:07:35Z
Google Scholar