Efficient parallel algorithms for parameterized problems
From MaRDI portal
Publication:2319897
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
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
