Advice classes of parametrized tractability
From MaRDI portal
Publication:676315
DOI10.1016/S0168-0072(95)00020-8zbMATH Open0873.68071OpenAlexW2064252342MaRDI QIDQ676315FDOQ676315
Authors: Michael R. Fellows, Liming Cai, Jianer 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
Recommendations
- Corrigendum to: ``Advice classes of parameterized tractability
- The structure of logarithmic advice complexity classes
- Bounding the complexity of advice functions
- The advice complexity of a class of hard online problems
- Advice complexity for a class of online problems
- Nondeterministic Instance Complexity and Proof Systems with Advice
- Advice Automatic Structures and Uniformly Automatic Classes
- Complexity-Restricted Advice Functions
- Advice complexity and barely random algorithms
- Advice complexity and barely random algorithms
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Title not available (Why is that?)
- Graph minors. XX: Wagner's conjecture
- Graph minors. XIII: The disjoint paths problem
- Title not available (Why is that?)
- Word Problems Solvable in Logspace
- Title not available (Why is that?)
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Title not available (Why is that?)
- Nondeterminism within $P^ * $
- Title not available (Why is that?)
- Two strikes against perfect phylogeny
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the parameterized complexity of short computation and factorization
- Title not available (Why is that?)
- On the Complexity of Covering Vertices by Faces in a Planar Graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (38)
- Studies in Computational Aspects of Voting
- Kernelization: new upper and lower bound techniques
- The structure of logarithmic advice complexity classes
- A shortcut to (sun)flowers: kernels in logarithmic space or linear time
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Incremental list coloring of graphs, parameterized by conservation
- The birth and early years of parameterized complexity
- Corrigendum to: ``Advice classes of parameterized tractability
- Infeasibility of instance compression and succinct PCPs for NP
- On problems without polynomial kernels
- A general method to speed up fixed-parameter-tractable algorithms
- Computing Hitting Set Kernels By AC^0-Circuits
- On the parametric complexity of schedules to minimize tardy tasks.
- On the parallel parameterized complexity of MaxSAT variants
- Faster existential FO model checking on posets
- Win-win kernelization for degree sequence completion problems
- Title not available (Why is that?)
- Finding points in general position
- On the space and circuit complexity of parameterized problems: classes and completeness
- Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- A parametric analysis of the state-explosion problem in model checking
- What Is Known About Vertex Cover Kernelization?
- The complexity of degree anonymization by vertex addition
- Approximation in (Poly-) Logarithmic Space
- Surfing with Rod
- Space-efficient graph kernelizations
- Computing kernels in parallel: lower and upper bounds
- Kernels in planar digraphs
- New limits to classical and quantum instance compression
- Parameterized analysis and crossing minimization problems
- Describing parameterized complexity classes
- Fractals for kernelization lower bounds
- The parameterized space complexity of embedding along a path
- Advice Automatic Structures and Uniformly Automatic Classes
- Parameterized complexity of critical node cuts
- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- Approximation in (poly-) logarithmic space
This page was built for publication: Advice classes of parametrized tractability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676315)
