Modular-width: an auxiliary parameter for parameterized parallel complexity

DOI10.1007/978-3-319-59605-1_13MaRDI QIDQ4632210zbMATH OpenOpenAlexFDO

Authors Faisal N. Abu-Khzam, Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, 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

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

Recommendations

• Parameterized Algorithms for Modular-Width
• Efficient parallel algorithms for parameterized problems
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• scientific article; zbMATH DE number 6850484
• The parameterised complexity of computing the maximum modularity of a graph

Cites work

• A survey of the algorithmic aspects of modular decomposition
• Algorithmic lower bounds for problems parameterized by clique-width
• Boolean-width of graphs
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Clique-width: on the price of generality
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Efficient parallel modular decomposition (extended abstract)
• scientific article; zbMATH DE number 1305047 (Why is no real title available?)
• Intractability of clique-width parameterizations
• On the parameterized parallel complexity and the vertex cover problem
• Parameterized Algorithms for Modular-Width
• Partitive hypergraphs
• Rank-width and vertex-minors
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth: Characterizations, Applications, and Computations
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)

Cited in

(11)

• Efficient parallel algorithms for parameterized problems
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• Trade-Offs between Depth and Width in Parallel Computation
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
• Local Gathering of Mobile Robots in Three Dimensions
• Cograph editing: Merging modules is equivalent to editing P₄s
• Immunization in the threshold model: a parameterized complexity study
• Parameterized complexity for iterated type partitions and modular-width
• Getting linear time in graphs of bounded neighborhood diversity
• The parameterised complexity of computing the maximum modularity of a graph

This page was built for publication: Modular-width: an auxiliary parameter for parameterized parallel complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4632210)