On the public citation graph
Power indices and easier hard problems
0 signed · 57 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/3-540-10291-4_20openalex-snapshot
Bounding the bandwidth of NP-complete problems
inferredcites →https://doi.org/10.1007/3-540-19488-6_105openalex-snapshot
Problems easy for tree-decomposable graphs extended abstract
inferredcites →https://doi.org/10.1007/978-1-4684-2001-2_9openalex-snapshot
Reducibility among Combinatorial Problems
inferredcites →https://doi.org/10.1007/978-3-540-68279-0_8openalex-snapshot
Reducibility Among Combinatorial Problems
inferredcites →https://doi.org/10.1016/0020-0190(87)90206-7openalex-snapshot
An application of the planar separator theorem to counting problems
inferredcites →https://doi.org/10.1016/0020-0190(88)90152-4openalex-snapshot
Short propositional formulas represent nondeterministic computations
inferredcites →https://doi.org/10.1016/0196-6774(86)90023-4openalex-snapshot
Graph minors. II. Algorithmic aspects of tree-width
inferredcites →https://doi.org/10.1016/0304-3975(77)90012-3openalex-snapshot
The Euclidean travelling salesman problem is NP-complete
inferredcites →https://doi.org/10.1080/00207168208803302openalex-snapshot
Linear time transformations between combinatorial problems
inferredcites →https://doi.org/10.1137/0209046openalex-snapshot
Applications of a Planar Separator Theorem
inferredcites →https://doi.org/10.1137/0211004openalex-snapshot
Dynamic Programming is Optimal for Nonserial Optimization Problems
inferredcites →https://doi.org/10.1137/0216059openalex-snapshot
Nonlinear Algebra and Optimization on Rings are “Hard”
inferredcites →https://doi.org/10.1137/0219003openalex-snapshot
The Complexity of Very Simple Boolean Formulas with Applications
inferredcites →https://doi.org/10.1145/322047.322060openalex-snapshot
Satisfiability Is Quasilinear Complete in NQL
inferredcites →https://doi.org/10.1145/800113.803626openalex-snapshot
Some NP-complete geometric problems
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)
inferredcites →https://doi.org/10.1145/800125.804030openalex-snapshot
On the time and tape complexity of languages I
inferredcites →https://doi.org/10.1145/800133.804350openalex-snapshot
The complexity of satisfiability problems
inferredcites →https://doi.org/10.1145/800157.805047openalex-snapshot
The complexity of theorem-proving procedures
inferredcites →https://doi.org/10.2307/j.ctv346t9c.13openalex-snapshot
The traveling salesman problem:
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferred← citeshttps://doi.org/10.1006/jpdc.1996.0150openalex-snapshot
Fast and Scalable Parallel Algorithms for Knapsack-like Problems
inferred← citeshttps://doi.org/10.1007/3-540-45465-9_2openalex-snapshot
Towards a Predictive Computational Complexity Theory
inferred← citeshttps://doi.org/10.1007/3-540-45622-8_18openalex-snapshot
Approximation of Relations by Propositional Formulas: Complexity and Semantics
inferred← citeshttps://doi.org/10.1007/3-540-45793-3_27openalex-snapshot
Local Problems, Planar Local Problems and Linear Time
inferred← citeshttps://doi.org/10.1007/3-540-57785-8_134openalex-snapshot
Quasilinear time complexity theory
inferred← citeshttps://doi.org/10.1007/978-1-4020-9688-4_11openalex-snapshot
Sums-of-Products and Subproblem Independence
inferred← citeshttps://doi.org/10.1007/978-1-4615-3422-8_31openalex-snapshot
Parallel Algorithms for NP-Complete Problems
inferred← citeshttps://doi.org/10.1007/978-1-4757-3145-3_18openalex-snapshot
On the Efficient Approximability of “HARD” Problems: A Survey
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/bf02127798openalex-snapshot
Sorting, linear time and the satisfiability problem
inferred← citeshttps://doi.org/10.1007/s00224-004-1160-8openalex-snapshot
Resource Bounds and Subproblem Independence
inferred← citeshttps://doi.org/10.1007/s10472-016-9521-yopenalex-snapshot
Refining complexity analyses in planning by exploiting the exponential time hypothesis
inferred← citeshttps://doi.org/10.1016/0304-3975(94)00182-iopenalex-snapshot
The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00031-qopenalex-snapshot
On quasilinear-time complexity theory
inferred← citeshttps://doi.org/10.1016/b978-0-12-708240-0.50009-5openalex-snapshot
The Complexity of Structural Containment and Equivalence
inferred← citeshttps://doi.org/10.1016/j.tcs.2007.04.026openalex-snapshot
Predecessor existence problems for finite discrete dynamical systems
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00017-6openalex-snapshot
New methods for 3-SAT decision and worst-case analysis
inferred← citeshttps://doi.org/10.1090/dimacs/035/05openalex-snapshot
Complexity of hierarchically and 1-dimensional periodically specified problems. I: Hardness results
inferred← citeshttps://doi.org/10.1109/cwit.2015.7255176openalex-snapshot
Empirical support for the high-density subset sum decision threshold
inferred← citeshttps://doi.org/10.1109/focs.2010.59openalex-snapshot
Subexponential Algorithms for Unique Games and Related Problems
inferred← citeshttps://doi.org/10.1109/sct.1994.315789openalex-snapshot
Generalized CNF satisfiability problems and non-efficient approximability
inferred← citeshttps://doi.org/10.1109/sct.1995.514727openalex-snapshot
On superlinear lower bounds in complexity theory
inferred← citeshttps://doi.org/10.1109/sfcs.1998.743516openalex-snapshot
Which problems have strongly exponential complexity?
inferred← citeshttps://doi.org/10.1137/1.9781611974782.141openalex-snapshot
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
inferred← citeshttps://doi.org/10.1137/s0097539793243004openalex-snapshot
An Algebraic Model for Combinatorial Problems
inferred← citeshttps://doi.org/10.1142/s0129054115500318openalex-snapshot
Complement, Complexity, and Symmetric Representation
inferred← citeshttps://doi.org/10.1145/1806689.1806724openalex-snapshot
On the complexity of circuit satisfiability
inferred← citeshttps://doi.org/10.1145/193820.193839openalex-snapshot
The quasilinear isomorphism challenge
inferred← citeshttps://doi.org/10.1145/2775105openalex-snapshot
Subexponential Algorithms for Unique Games and Related Problems
inferred← citeshttps://doi.org/10.1145/3196275openalex-snapshot
Completeness for First-order Properties on Sparse Structures with Algorithmic Applications
inferred← citeshttps://doi.org/10.1145/602382.602409openalex-snapshot
Deterministic versus nondeterministic time and lower bound problems
inferred← citeshttps://doi.org/10.48550/arxiv.cs/0102019openalex-snapshot
Easy and Hard Constraint Ranking in OT: Algorithms and 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.