Using nondeterminism to design efficient deterministic algorithms

DOI10.1007/s00453-004-1096-zzbMath1088.68835OpenAlexW2085521211MaRDI QIDQ1882527

Donald K. Friesen, Wei-Jia Jia, Iyad A. Kanj, Jian'er Chen

Publication date: 1 October 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-004-1096-z

zbMATH Keywords

Parameterized algorithmsNondeterministic algorithmsThree-dimensional matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) General topics in the theory of algorithms (68W01)

Related Items (13)

Mixing Color Coding-Related Techniques ⋮ Parameterized approximation algorithms for packing problems ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets ⋮ Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters ⋮ An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem ⋮ Confronting intractability via parameters ⋮ Improved deterministic algorithms for weighted matching and packing problems ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ The \(k\)-distinct language: parameterized automata constructions ⋮ Unnamed Item ⋮ An improved FPT algorithm for the flip distance problem ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness

This page was built for publication: Using nondeterminism to design efficient deterministic algorithms