---
_id: '82'
abstract:
- lang: eng
  text: 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.
author:
- first_name: Faisal N.
  full_name: Abu-Khzam, Faisal N.
  last_name: Abu-Khzam
- first_name: Shouwei
  full_name: Li, Shouwei
  last_name: Li
- first_name: Christine
  full_name: Markarian, Christine
  id: '37612'
  last_name: Markarian
- first_name: Friedhelm
  full_name: Meyer auf der Heide, Friedhelm
  id: '15523'
  last_name: Meyer auf der Heide
- first_name: Pavel
  full_name: Podlipyan, Pavel
  last_name: Podlipyan
citation:
  ama: 'Abu-Khzam FN, Li S, Markarian C, Meyer auf der Heide F, Podlipyan P. Modular-Width:
    An Auxiliary Parameter for Parameterized Parallel Complexity. In: <i>Proceedings
    of the 11th International Workshop on Frontiers in Algorithmics (FAW)</i>. LNCS.
    ; 2017:139-150. doi:<a href="https://doi.org/10.1007/978-3-319-59605-1_13">10.1007/978-3-319-59605-1_13</a>'
  apa: 'Abu-Khzam, F. N., Li, S., Markarian, C., Meyer auf der Heide, F., &#38; Podlipyan,
    P. (2017). Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity.
    In <i>Proceedings of the 11th International Workshop on Frontiers in Algorithmics
    (FAW)</i> (pp. 139–150). <a href="https://doi.org/10.1007/978-3-319-59605-1_13">https://doi.org/10.1007/978-3-319-59605-1_13</a>'
  bibtex: '@inproceedings{Abu-Khzam_Li_Markarian_Meyer auf der Heide_Podlipyan_2017,
    series={LNCS}, title={Modular-Width: An Auxiliary Parameter for Parameterized
    Parallel Complexity}, DOI={<a href="https://doi.org/10.1007/978-3-319-59605-1_13">10.1007/978-3-319-59605-1_13</a>},
    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} }'
  chicago: '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 <i>Proceedings of the 11th International
    Workshop on Frontiers in Algorithmics (FAW)</i>, 139–50. LNCS, 2017. <a href="https://doi.org/10.1007/978-3-319-59605-1_13">https://doi.org/10.1007/978-3-319-59605-1_13</a>.'
  ieee: '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 <i>Proceedings of the 11th International Workshop on Frontiers in Algorithmics
    (FAW)</i>, 2017, pp. 139–150.'
  mla: 'Abu-Khzam, Faisal N., et al. “Modular-Width: An Auxiliary Parameter for Parameterized
    Parallel Complexity.” <i>Proceedings of the 11th International Workshop on Frontiers
    in Algorithmics (FAW)</i>, 2017, pp. 139–50, doi:<a href="https://doi.org/10.1007/978-3-319-59605-1_13">10.1007/978-3-319-59605-1_13</a>.'
  short: '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.'
date_created: 2017-10-17T12:41:07Z
date_updated: 2022-01-06T07:03:52Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/978-3-319-59605-1_13
file:
- access_level: closed
  content_type: application/pdf
  creator: ups
  date_created: 2018-11-02T15:07:35Z
  date_updated: 2018-11-02T15:07:35Z
  file_id: '5294'
  file_name: Modular-WidthAnAuxiliaryParame.pdf
  file_size: 238276
  relation: main_file
  success: 1
file_date_updated: 2018-11-02T15:07:35Z
has_accepted_license: '1'
language:
- iso: eng
page: 139-150
project:
- _id: '1'
  name: SFB 901
- _id: '2'
  name: SFB 901 - Project Area A
- _id: '5'
  name: SFB 901 - Subproject A1
publication: Proceedings of the 11th International Workshop on Frontiers in Algorithmics
  (FAW)
series_title: LNCS
status: public
title: 'Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity'
type: conference
user_id: '477'
year: '2017'
...