Efficient parallel algorithms for parameterized problems

DOI10.1016/j.tcs.2018.11.006zbMath1429.68327OpenAlexW2900662096WikidataQ128930741 ScholiaQ128930741MaRDI QIDQ2319897

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

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

vertex covermodular widthparameterized parallel complexity

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improvement on parallel computation of a maximal matching
• Improved upper bounds for vertex cover
• Boolean-width of graphs
• Partitive hypergraphs
• Characterizing multiterminal flow networks and computing flows in networks of small treewidth
• Crown structures for vertex cover kernelization
• Scalable parallel algorithms for FPT problems
• 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
• Parallel breadth-first search algorithms for trees and graphs
• Treewidth: Characterizations, Applications, and Computations
• A universal interconnection pattern for parallel computers
• A New Algorithm for Generating All the Maximal Independent Sets
• Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Slicewise Definability in First-Order Logic with Bounded Quantifier Rank.
• Paths, Trees, and Flowers
• Parallelism in random access machines
• Graph-Theoretic Concepts in Computer Science

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