On the public citation graph

Parameterized Problems Complete for Nondeterministic Fpt Time and Logarithmic Space

https://doi.org/10.2139/ssrn.4673490
0 signed · 49 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.1007/978-1-4471-5559-1openalex-extracted
Fundamentals of Parameterized Complexity
inferredcites →https://doi.org/10.1007/978-1-4612-0515-9openalex-extracted
Parameterized Complexity
inferredcites →https://doi.org/10.1007/978-3-030-42071-0_2openalex-extracted
Collaborating with Hans: Some Remaining Wonderments
inferredcites →https://doi.org/10.1007/978-3-030-86838-3_2openalex-extracted
Parameterized Complexity of Bandwidth of Caterpillars and Weighted Path Emulation
inferredcites →https://doi.org/10.1007/978-3-031-15914-5_7openalex-extracted
Problems Hard for Treewidth but Easy for Stable Gonality
inferredcites →https://doi.org/10.1007/978-3-031-49275-4_14openalex-extracted
Upward and Orthogonal Planarity are W[1]-Hard Parameterized by Treewidth
inferredcites →https://doi.org/10.1007/978-3-031-52113-3_12openalex-extracted
On the Parameterized Complexity of the Perfect Phylogeny Problem
inferredcites →https://doi.org/10.1007/978-3-319-21275-3openalex-extracted
Parameterized Algorithms
inferredcites →https://doi.org/10.1007/978-3-540-73556-4_38openalex-extracted
On the Complexity of Some Colorful Problems Parameterized by Treewidth
inferredcites →https://doi.org/10.1007/978-3-642-39206-1_17openalex-extracted
Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
inferredcites →https://doi.org/10.1007/978-3-662-43948-7_34openalex-extracted
Parameterized Complexity of Bandwidth on Trees
inferredcites →https://doi.org/10.1007/978-3-662-44777-2_1openalex-extracted
Losing Weight by Gaining Edges
inferredcites →https://doi.org/10.1007/bf02280884openalex-extracted
The NP-Completeness of the bandwidth minimization problem
inferredcites →https://doi.org/10.1007/s00453-014-9944-yopenalex-extracted
On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness
inferredcites →https://doi.org/10.1007/s00453-024-01274-9openalex-extracted
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
inferredcites →https://doi.org/10.1007/s10951-017-0519-zopenalex-extracted
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
inferredcites →https://doi.org/10.1016/0167-6377(95)00031-9openalex-extracted
W[2]-hardness of precedence constrained K-processor scheduling
inferredcites →https://doi.org/10.1016/0196-6774(84)90006-3openalex-extracted
Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-extracted
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(94)00097-3openalex-extracted
Fixed-parameter tractability and completeness II: On completeness for W[1]
inferredcites →https://doi.org/10.1016/0890-5401(90)90027-fopenalex-extracted
The complexity of finding uniform emulations on paths and ring networks
inferredcites →https://doi.org/10.1016/j.ic.2010.11.026openalex-extracted
On the complexity of some colorful problems parameterized by treewidth
inferredcites →https://doi.org/10.1016/j.ic.2014.12.008openalex-extracted
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
inferredcites →https://doi.org/10.1016/j.tcs.2008.09.065openalex-extracted
On the parameterized complexity of multiple-interval graph problems
inferredcites →https://doi.org/10.1016/s0022-0000(03)00078-3openalex-extracted
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
inferredcites →https://doi.org/10.1016/s0166-218x(96)00085-6openalex-extracted
Generalized coloring for tree-like graphs
inferredcites →https://doi.org/10.1016/s0304-3975(98)00342-9openalex-extracted
The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
inferredcites →https://doi.org/10.1093/bioinformatics/11.1.49openalex-extracted
Parameterized complexity analysis in computational biology
inferredcites →https://doi.org/10.1109/ccc.2003.1214407openalex-extracted
Bounded nondeterminism and alternation in parameterized complexity theory
inferredcites →https://doi.org/10.1109/focs.2010.21openalex-extracted
Logspace Versions of the Theorems of Bodlaender and Courcelle
inferredcites →https://doi.org/10.1109/focs52979.2021.00027openalex-extracted
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
inferredcites →https://doi.org/10.1109/tc.1982.1675994openalex-extracted
Quotient Networks
inferredcites →https://doi.org/10.1137/0406014openalex-extracted
The Pathwidth and Treewidth of Cographs
inferredcites →https://doi.org/10.1137/0601042openalex-extracted
Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
inferredcites →https://doi.org/10.1137/0607057openalex-extracted
The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
inferredcites →https://doi.org/10.1137/s0097539792228228openalex-extracted
Fixed-Parameter Tractability and Completeness I: Basic Results
inferredcites →https://doi.org/10.1137/s0097539793258143openalex-extracted
Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
inferredcites →https://doi.org/10.1137/s0895480194275825openalex-extracted
Algorithms for Vertex Partitioning Problems on Partial k-Trees
inferredcites →https://doi.org/10.1145/3154856openalex-extracted
On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
inferredcites →https://doi.org/10.1145/3170442openalex-extracted
Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
inferredcites →https://doi.org/10.21203/rs.3.rs-2049659/v1openalex-extracted
inferredcites →https://doi.org/10.4230/lipics.esa.2022.24openalex-extracted
List Colouring Trees in Logarithmic Space
inferredcites →https://doi.org/10.4230/lipics.icalp.2023.27openalex-extracted
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters
inferredcites →https://doi.org/10.4230/lipics.ipec.2022.6openalex-extracted
On the Complexity of Problems on Tree-Structured Graphs
inferredcites →https://doi.org/10.4230/lipics.ipec.2023.6openalex-extracted
Problems hard for treewidth but easy for stable gonality
inferredcites →https://doi.org/10.46298/dmtcs.12540openalex-extracted
On the parameterized complexity of computing tree-partitions
inferredcites →https://doi.org/10.48550/arxiv.2209.07772openalex-extracted
$b$-Coloring Parameterized by Pathwidth is XNLP-complete
inferredcites →https://doi.org/10.1007/s00453-026-01381-9openalex-snapshot
Parameterized Complexities of Dominating and Independent Set Reconfiguration
inferredcites →https://doi.org/10.4230/lipics.ipec.2022.3openalex-snapshot
On the Hardness of Generalized Domination Problems Parameterized by Mim-Width
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.