On the Parameterized Parallel Complexity and the Vertex Cover Problem

DOI10.1007/978-3-319-48749-6_35zbMath1483.68146OpenAlexW2542186661MaRDI QIDQ2958339

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

Publication date: 1 February 2017

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-48749-6_35

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity ⋮ Efficient parallel algorithms for parameterized problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Improved upper bounds for vertex cover
• An improved parallel algorithm for maximal matching
• Crown structures for vertex cover kernelization
• The Monotone Circuit Value Problem with Bounded Genus Is in NC
• A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
• Parallel breadth-first search algorithms for trees and graphs
• The Polynomially Bounded Perfect Matching Problem Is in NC 2
• A fast parallel algorithm for routing in permutation networks
• On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• Embedding and canonizing graphs of bounded genus in logspace
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: On the Parameterized Parallel Complexity and the Vertex Cover Problem