### 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.

Original language | English |
---|---|

Title of host publication | Frontiers in Algorithmics |

Editors | Mingyu Xiao, Frances Rosamond |

Publisher | Springer, Cham |

Pages | 139-150 |

Number of pages | 12 |

ISBN (Electronic) | 9783319596051 |

ISBN (Print) | 9783319596044 |

DOIs | |

Publication status | Published - 2017 |

Event | 11th International Frontiers of Algorithmics Workshop, FAW 2017 - Chengdu, China Duration: 23 Jun 2017 → 25 Jun 2017 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 10336 |

ISSN (Print) | 0302-9743 |

### Conference

Conference | 11th International Frontiers of Algorithmics Workshop, FAW 2017 |
---|---|

Country | China |

City | Chengdu |

Period | 23/06/17 → 25/06/17 |

## Fingerprint Dive into the research topics of 'Modular-width: An auxiliary parameter for parameterized parallel complexity'. Together they form a unique fingerprint.

## Cite this

*Frontiers in Algorithmics*(pp. 139-150). (Lecture Notes in Computer Science; Vol. 10336). Springer, Cham. https://doi.org/10.1007/978-3-319-59605-1_13