Using nondeterminism to design efficient deterministic algorithms
From MaRDI portal
Publication:1882527
DOI10.1007/s00453-004-1096-zzbMath1088.68835MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68W40: Analysis of algorithms
68W01: General topics in the theory of algorithms
Related Items
Unnamed Item, The \(k\)-distinct language: parameterized automata constructions, Parameterized approximation algorithms for packing problems, 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, An improved FPT algorithm for the flip distance problem, An \(O^{*}(3.53^{3k})\)-time parameterized algorithm for the 3-set packing problem, Parameterized computation and complexity: a new approach dealing with NP-hardness, Parameterized counting matching and packing: a family of hard problems that admit FPTRAS, Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets, Mixing Color Coding-Related Techniques, Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
