Solving large FPT problems on coarse-grained parallel machines

DOI10.1016/S0022-0000(03)00075-8zbMath1114.68428MaRDI QIDQ1877701

Peter J. Taillon, Ulrike Stege, Andrew Rau-Chaplin, James Cheetham, Frank Dehne

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Related Items

Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ A Basic Parameterized Complexity Primer ⋮ Strong computational lower bounds via parameterized complexity ⋮ Approximation for vertex cover in \(\beta\)-conflict graphs ⋮ On the approximability of the link building problem ⋮ Vertex cover problem parameterized above and below tight bounds ⋮ Towards optimal kernel for edge-disjoint triangle packing ⋮ Confronting intractability via parameters ⋮ Properties of vertex cover obstructions ⋮ Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs ⋮ Improved upper bounds for vertex cover ⋮ Linear kernelizations for restricted 3-Hitting Set problems ⋮ Parameterized Complexity ⋮ Tight lower bounds for certain parameterized NP-hard problems ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness

Cites Work

• An improved fixed-parameter algorithm for vertex cover
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Special issue: Coarse-grained parallel algorithms
• On limited nondeterminism and the complexity of the V-C dimension
• Nondeterminism within $P^ * $
• Fixed-Parameter Tractability and Completeness I: Basic Results
• SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MULTICOMPUTERS
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item