Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity

DOI10.1007/978-3-319-59605-1_13zbMath1429.68326OpenAlexW2618066705MaRDI QIDQ4632210

Shouwei Li, Friedhelm Meyer auf der Heide, Faisal N. Abu-Khzam, Christine Markarian, Pavel Podlipyan

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-59605-1_13

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Local Gathering of Mobile Robots in Three Dimensions ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ Cograph editing: Merging modules is equivalent to editing P_4s ⋮ Efficient parallel algorithms for parameterized problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of the algorithmic aspects of modular decomposition
• Boolean-width of graphs
• Partitive hypergraphs
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Rank-width and vertex-minors
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Parameterized Algorithms for Modular-Width
• When Trees Grow Low: Shrubs and Fast MSO1
• On the Parameterized Parallel Complexity and the Vertex Cover Problem
• Intractability of Clique-Width Parameterizations
• Treewidth: Characterizations, Applications, and Computations
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Efficient parallel modular decomposition (extended abstract)