Advice classes of parametrized tractability
From MaRDI portal
Publication:676315
DOI10.1016/S0168-0072(95)00020-8zbMath0873.68071OpenAlexW2064252342MaRDI QIDQ676315
Michael R. Fellows, Li-Ming Cai, Jian'er Chen, Rodney G. Downey
Publication date: 2 November 1997
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0168-0072(95)00020-8
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (34)
On the parametric complexity of schedules to minimize tardy tasks. ⋮ Describing parameterized complexity classes ⋮ Win-win kernelization for degree sequence completion problems ⋮ New Limits to Classical and Quantum Instance Compression ⋮ Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues] ⋮ Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control ⋮ The Birth and Early Years of Parameterized Complexity ⋮ Studies in Computational Aspects of Voting ⋮ Parameterized analysis and crossing minimization problems ⋮ The parameterized space complexity of embedding along a path ⋮ Computing Hitting Set Kernels By AC^0-Circuits ⋮ A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ The complexity of degree anonymization by vertex addition ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Finding Points in General Position ⋮ Unnamed Item ⋮ Corrigendum to: ``Advice classes of parameterized tractability ⋮ Fractals for Kernelization Lower Bounds ⋮ Surfing with Rod ⋮ Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits ⋮ Parameterized complexity of critical node cuts ⋮ Kernels in planar digraphs ⋮ A parametric analysis of the state-explosion problem in model checking ⋮ Approximation in (Poly-) logarithmic space ⋮ Faster Existential FO Model Checking on Posets ⋮ Approximation in (Poly-) Logarithmic Space ⋮ On problems without polynomial kernels ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover ⋮ Unnamed Item ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ A general method to speed up fixed-parameter-tractable algorithms
Cites Work
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Graph minors. XX: Wagner's conjecture
- On the parameterized complexity of short computation and factorization
- Graph minors. XIII: The disjoint paths problem
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- On the Complexity of Covering Vertices by Faces in a Planar Graph
- Word Problems Solvable in Logspace
- Nondeterminism within $P^ * $
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Two strikes against perfect phylogeny
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Advice classes of parametrized tractability
