On the public citation graph

Bounded fixed-parameter tractability and log 2 n nondeterministic bits

0 signed · 56 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/jcss.1996.0058openalex-snapshot
On Limited Nondeterminism and the Complexity of the V-C Dimension
inferredcites →https://doi.org/10.1006/jcss.1998.1602openalex-snapshot
Deciding the Vapnik–Červonenkis Dimension is∑p3-complete
inferredcites →https://doi.org/10.1006/jcss.1999.1626openalex-snapshot
On the Complexity of Database Queries
inferredcites →https://doi.org/10.1007/978-1-4612-0515-9openalex-snapshot
Parameterized Complexity
inferredcites →https://doi.org/10.1007/978-3-540-28639-4_5openalex-snapshot
Bounded Fixed-Parameter Tractability: The Case 2poly( k)
inferredcites →https://doi.org/10.1007/978-3-662-03088-2_3openalex-snapshot
Computational Complexity
inferredcites →https://doi.org/10.1016/0168-0072(94)00034-zopenalex-snapshot
Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues
inferredcites →https://doi.org/10.1016/b978-0-444-88074-1.50010-xopenalex-snapshot
Graph Rewriting: An Algebraic and Logic Approach
inferredcites →https://doi.org/10.1016/s1571-0661(04)00301-9openalex-snapshot
Parameterized Complexity
inferredcites →https://doi.org/10.1090/dimacs/039/07openalex-snapshot
Descriptive complexity and the 𝑊 hierarchy
inferredcites →https://doi.org/10.1109/ccc.2003.1214417openalex-snapshot
Parameterized complexity for the skeptic
inferredcites →https://doi.org/10.1109/lics.2002.1029830openalex-snapshot
The complexity of first-order and monadic second-order logic revisited
inferredcites →https://doi.org/10.1137/0209003openalex-snapshot
Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
inferredcites →https://doi.org/10.1137/s0097539799360768openalex-snapshot
Fixed-Parameter Tractability, Definability, and Model-Checking
inferredcites →https://doi.org/10.1145/168304.168311openalex-snapshot
Parameterized learning complexity
inferredcites →https://doi.org/10.1145/509907.509912openalex-snapshot
New results on monotone dualization and generating hypergraph transversals
inferredcites →https://doi.org/10.1145/602220.602222openalex-snapshot
Query evaluation via tree-decompositions
inferredcites →https://doi.org/10.1145/637411.637428openalex-snapshot
Parameterized complexity for the database theorist
inferredcites →https://doi.org/10.2168/lmcs-1(1:2)2005openalex-snapshot
Model-Checking Problems as a Basis for Parameterized Intractability

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/11733492_9openalex-snapshot
Transaction Databases, Frequent Itemsets, and Their Condensed Representations
inferred← citeshttps://doi.org/10.1007/11847250_18openalex-snapshot
The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
inferred← citeshttps://doi.org/10.1007/11847250_3openalex-snapshot
The Parameterized Complexity of Maximality and Minimality Problems
inferred← citeshttps://doi.org/10.1007/978-1-4471-5559-1_22openalex-snapshot
Some Other W[1] Hardness Results
inferred← citeshttps://doi.org/10.1007/978-1-4471-5559-1_26openalex-snapshot
Fixed Parameter Analogues of PSpace and k-Move Games
inferred← citeshttps://doi.org/10.1007/978-1-4471-5559-1_29openalex-snapshot
The M-Hierarchy, and XP-Optimality
inferred← citeshttps://doi.org/10.1007/978-1-4471-5559-1_30openalex-snapshot
Kernelization Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-540-28629-5_4openalex-snapshot
Ubiquitous Parameterization — Invitation to Fixed-Parameter Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-540-28639-4_10openalex-snapshot
On Miniaturized Problems in Parameterized Complexity Theory
inferred← citeshttps://doi.org/10.1007/978-3-540-28639-4_5openalex-snapshot
Bounded Fixed-Parameter Tractability: The Case 2poly( k)
inferred← citeshttps://doi.org/10.1007/978-3-540-30550-7_2openalex-snapshot
Some New Directions and Questions in Parameterized Complexity
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_46openalex-snapshot
On Problems without Polynomial Kernels (Extended Abstract)
inferred← citeshttps://doi.org/10.1007/978-3-540-73001-9_29openalex-snapshot
Parameterized Complexity and Logic
inferred← citeshttps://doi.org/10.1007/978-3-540-74915-8_30openalex-snapshot
Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
inferred← citeshttps://doi.org/10.1007/978-3-642-11269-0_4openalex-snapshot
Planar Capacitated Dominating Set Is W[1]-Hard
inferred← citeshttps://doi.org/10.1007/978-3-642-32589-2_2openalex-snapshot
New Races in Parameterized Algorithmics
inferred← citeshttps://doi.org/10.1007/s00224-011-9381-0openalex-snapshot
Parameterized Random Complexity
inferred← citeshttps://doi.org/10.1016/j.apal.2007.06.001openalex-snapshot
Bounded fixed-parameter tractability and reducibility
inferred← citeshttps://doi.org/10.1016/j.apal.2007.09.003openalex-snapshot
The parameterized complexity of maximality and minimality problems
inferred← citeshttps://doi.org/10.1016/j.cosrev.2011.09.002openalex-snapshot
Confronting intractability via parameters
inferred← citeshttps://doi.org/10.1016/j.geoforum.2007.05.009openalex-snapshot
Coupled and complex: Human–environment interaction in the Greater Yellowstone Ecosystem, USA
inferred← citeshttps://doi.org/10.1016/j.jcss.2009.04.001openalex-snapshot
On problems without polynomial kernels
inferred← citeshttps://doi.org/10.1093/comjnl/bxm036openalex-snapshot
On Parameterized Intractability: Hardness and Completeness
inferred← citeshttps://doi.org/10.1093/logcom/exaf049openalex-snapshot
The logics for the complexity classes with limited non-determinism
inferred← citeshttps://doi.org/10.1093/logcom/exn029openalex-snapshot
Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
inferred← citeshttps://doi.org/10.1109/ccc.2006.8openalex-snapshot
An Isomorphism between Subexponential and Parameterized Complexity Theory
inferred← citeshttps://doi.org/10.1109/ccc.2007.21openalex-snapshot
On Parameterized Path and Chordless Path Problems
inferred← citeshttps://doi.org/10.1109/focs.2006.54openalex-snapshot
On the Compressibility of NP Instances and Cryptographic Applications
inferred← citeshttps://doi.org/10.1137/070687153openalex-snapshot
An Isomorphism Between Subexponential and Parameterized Complexity Theory
inferred← citeshttps://doi.org/10.1137/10080703xopenalex-snapshot
Improving Exhaustive Search Implies Superpolynomial Lower Bounds
inferred← citeshttps://doi.org/10.1137/15m1027267openalex-snapshot
Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic
inferred← citeshttps://doi.org/10.1137/15m1036579openalex-snapshot
Hybridization Number on Three Rooted Binary Trees is EPT
inferred← citeshttps://doi.org/10.1137/16m1104834openalex-snapshot
Slightly Superexponential Parameterized Problems
inferred← citeshttps://doi.org/10.1145/1806689.1806723openalex-snapshot
Improving exhaustive search implies superpolynomial lower bounds
inferred← citeshttps://doi.org/10.1145/3618260.3649723openalex-snapshot
Self-Improvement for Circuit-Analysis Problems
inferred← citeshttps://doi.org/10.23638/lmcs-15(3:31)2019openalex-snapshot
The parameterized space complexity of model-checking bounded variable first-order logic
inferred← citeshttps://doi.org/10.48550/arxiv.1206.2436openalex-snapshot
A Proof Checking View of Parameterized Complexity
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.