Efficient parallel algorithms for parameterized problems

DOI10.1016/J.TCS.2018.11.006MaRDI QIDQ2319897zbMATH OpenOpenAlexWikidataFDO

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

Publication date 20 August 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.11.006

zbMATH Keywords

modular widthparameterized parallel complexityvertex cover

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

• Towards work-efficient parallel parameterized algorithms
• scientific article; zbMATH DE number 43583
• Efficient Parallel Algorithms for Parabolic Problems
• Efficient use of parallelism in algorithmic parameter optimization applications
• scientific article; zbMATH DE number 4039280
• scientific article; zbMATH DE number 3894470
• scientific article; zbMATH DE number 562239
• scientific article; zbMATH DE number 1305047
• scientific article; zbMATH DE number 1150245
• scientific article; zbMATH DE number 30939

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• A universal interconnection pattern for parallel computers
• Algorithmic lower bounds for problems parameterized by clique-width
• An improvement on parallel computation of a maximal matching
• Boolean-width of graphs
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Clique-width: on the price of generality
• Crown structures for vertex cover kernelization
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Fast parallel fixed-parameter algorithms via color coding
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 4047154 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Intractability of clique-width parameterizations
• Modular-width: an auxiliary parameter for parameterized parallel complexity
• On the parameterized parallel complexity and the vertex cover problem
• Parallel breadth-first search algorithms for trees and graphs
• Parallelism in random access machines
• Parameterized Algorithms for Modular-Width
• Partitive hypergraphs
• Paths, Trees, and Flowers
• Rank-width and vertex-minors
• Scalable parallel algorithms for FPT problems
• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
• 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

(10)

• Solving large FPT problems on coarse-grained parallel machines
• Scalable parallel algorithms for FPT problems
• On the parameterized parallel complexity and the vertex cover problem
• A Fast Parallel Horner Algorithm
• A taxonomy of problems with fast parallel algorithms
• Modular-width: an auxiliary parameter for parameterized parallel complexity
• Computing kernels in parallel: lower and upper bounds
• Towards work-efficient parallel parameterized algorithms
• Fast parallel fixed-parameter algorithms via color coding
• More efficient parallel flow algorithms

This page was built for publication: Efficient parallel algorithms for parameterized problems

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