TY - GEN

T1 - Modular-width

T2 - 11th International Frontiers of Algorithmics Workshop, FAW 2017

AU - Abu-Khzam, Faisal N.

AU - Li, Shouwei

AU - Markarian, Christine

AU - Meyer auf der Heide, Friedhelm

AU - Podlipyan, Pavel

PY - 2017

Y1 - 2017

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

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

UR - http://www.scopus.com/inward/record.url?scp=85021705618&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59605-1_13

DO - 10.1007/978-3-319-59605-1_13

M3 - Conference Paper published in Proceedings

AN - SCOPUS:85021705618

SN - 9783319596044

T3 - Lecture Notes in Computer Science

SP - 139

EP - 150

BT - Frontiers in Algorithmics

A2 - Xiao, Mingyu

A2 - Rosamond, Frances

PB - Springer, Cham

Y2 - 23 June 2017 through 25 June 2017

ER -