On the public citation graph
Tight Lower Bounds on Graph Embedding Problems
0 signed · 70 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.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferredcites →https://doi.org/10.1006/jctb.1995.1006openalex-snapshot
Graph Minors .XIII. The Disjoint Paths Problem
inferredcites →https://doi.org/10.1007/3-540-36478-1_17openalex-snapshot
Exact Algorithms for NP-Hard Problems: A Survey
inferredcites →https://doi.org/10.1007/3-540-44985-x_2openalex-snapshot
Coping with the NP-Hardness of the Graph Bandwidth Problem
inferredcites →https://doi.org/10.1007/978-3-319-21275-3_14openalex-snapshot
Lower Bounds Based on the Exponential-Time Hypothesis
inferredcites →https://doi.org/10.1007/978-3-540-70575-8_25openalex-snapshot
Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
inferredcites →https://doi.org/10.1007/978-3-540-79723-4openalex-snapshot
Parameterized and Exact Computation
inferredcites →https://doi.org/10.1007/978-3-540-79723-4_18openalex-snapshot
The Time Complexity of Constraint Satisfaction
inferredcites →https://doi.org/10.1007/978-3-642-16533-7openalex-snapshot
Exact Exponential Algorithms
inferredcites →https://doi.org/10.1007/s00224-007-2007-xopenalex-snapshot
Exact Algorithms for Graph Homomorphisms
inferredcites →https://doi.org/10.1007/s00224-010-9261-zopenalex-snapshot
New Plain-Exponential Time Classes for Graph Homomorphism
inferredcites →https://doi.org/10.1007/s00453-009-9302-7openalex-snapshot
Exact Algorithms for L(2,1)-Labeling of Graphs
inferredcites →https://doi.org/10.1007/s00453-010-9460-7openalex-snapshot
Fast Algorithms for max independent set
inferredcites →https://doi.org/10.1016/0020-0190(76)90065-xopenalex-snapshot
A note on the complexity of the chromatic number problem
inferredcites →https://doi.org/10.1016/0095-8956(90)90132-jopenalex-snapshot
On the complexity of H-coloring
inferredcites →https://doi.org/10.1016/0196-6774(86)90032-5openalex-snapshot
Algorithms for maximum independent sets
inferredcites →https://doi.org/10.1016/j.cosrev.2008.06.001openalex-snapshot
Locally constrained graph homomorphisms—structure, complexity, and applications
inferredcites →https://doi.org/10.1016/j.dam.2011.10.032openalex-snapshot
Bandwidth and distortion revisited
inferredcites →https://doi.org/10.1016/j.ipl.2014.02.012openalex-snapshot
Exact algorithm for graph homomorphism and locally injective graph homomorphism
inferredcites →https://doi.org/10.1016/j.jcss.2006.04.007openalex-snapshot
Strong computational lower bounds via parameterized complexity
inferredcites →https://doi.org/10.1016/j.jda.2008.10.003openalex-snapshot
An exact algorithm for subgraph homeomorphism
inferredcites →https://doi.org/10.1016/j.tcs.2011.02.043openalex-snapshot
An exact algorithm for minimum distortion embedding
inferredcites →https://doi.org/10.1016/j.tcs.2012.06.037openalex-snapshot
Fast exact algorithm for L(2,1) -labeling of graphs
inferredcites →https://doi.org/10.1093/acprof:oso/9780198528173.001.0001openalex-snapshot
Graphs and Homomorphisms
inferredcites →https://doi.org/10.1109/icca.2002.1229256openalex-snapshot
Mathematics and its applications
inferredcites →https://doi.org/10.1137/0110015openalex-snapshot
A Dynamic Programming Approach to Sequencing Problems
inferredcites →https://doi.org/10.1137/0405048openalex-snapshot
Labelling Graphs with a Condition at Distance 2
inferredcites →https://doi.org/10.1137/070683933openalex-snapshot
Set Partitioning via Inclusion-Exclusion
inferredcites →https://doi.org/10.1137/070711670openalex-snapshot
Towards Sharp Inapproximability for Any 2-CSP
inferredcites →https://doi.org/10.1137/080712921openalex-snapshot
Low Distortion Maps Between Point Sets
inferredcites →https://doi.org/10.1137/1.9780898715859openalex-snapshot
Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
inferredcites →https://doi.org/10.1137/100789403openalex-snapshot
Counting Subgraphs via Homomorphisms
inferredcites →https://doi.org/10.1137/110839229openalex-snapshot
Determinant Sums for Undirected Hamiltonicity
inferredcites →https://doi.org/10.1137/s0097539794266766openalex-snapshot
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
inferredcites →https://doi.org/10.1145/1060590.1060624openalex-snapshot
Low-distortion embeddings of general metrics into the line
inferredcites →https://doi.org/10.1145/1206035.1206036openalex-snapshot
The complexity of homomorphism and constraint satisfaction problems seen from the other side
inferredcites →https://doi.org/10.1145/1374376.1374414openalex-snapshot
Optimal algorithms and inapproximability results for every CSP?
inferredcites →https://doi.org/10.1145/1374376.1374488openalex-snapshot
Graphs, polymorphisms and the complexity of homomorphism problems
inferredcites →https://doi.org/10.1145/230514.571645openalex-snapshot
Introduction to the Theory of Computation
inferredcites →https://doi.org/10.1145/2489789openalex-snapshot
Distortion is Fixed Parameter Tractable
inferredcites →https://doi.org/10.1145/800029.808532openalex-snapshot
A dynamic programming approach to sequencing problems
inferredcites →https://doi.org/10.4230/dagrep.3.8.40openalex-snapshot
Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331)
inferredcites →https://doi.org/10.4230/dagsemproc.08431.1openalex-snapshot
08431 Abstracts Collection – Moderately Exponential Time Algorithms
inferredcites →https://doi.org/10.4230/lipics.stacs.2014.542openalex-snapshot
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-3-030-17402-6_8openalex-snapshot
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
inferred← citeshttps://doi.org/10.1007/978-3-030-83508-8_5openalex-snapshot
Pattern Matching in Doubling Spaces
inferred← citeshttps://doi.org/10.1007/s00453-020-00737-zopenalex-snapshot
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
inferred← citeshttps://doi.org/10.1007/s10458-025-09711-xopenalex-snapshot
Hedonic seat arrangement problems
inferred← citeshttps://doi.org/10.1007/s11128-016-1513-7openalex-snapshot
Identifying the minor set cover of dense connected bipartite graphs via random matching edge sets
inferred← citeshttps://doi.org/10.1016/j.cor.2025.107034openalex-snapshot
Multi-armed bandit for the cyclic minimum sitting arrangement problem
inferred← citeshttps://doi.org/10.1016/j.cosrev.2026.100919openalex-snapshot
An invitation to “Fine-grained complexity of NP-complete problems”
inferred← citeshttps://doi.org/10.1016/j.ipl.2026.106646openalex-snapshot
Coloring hardness on low twin-width graphs
inferred← citeshttps://doi.org/10.1137/1.9781611975994.97openalex-snapshot
Fine-grained complexity of graph homomorphism problem for bounded-treewidth graphs
inferred← citeshttps://doi.org/10.1137/1.9781611976465.139openalex-snapshot
The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid
inferred← citeshttps://doi.org/10.1137/20m1320146openalex-snapshot
Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs
inferred← citeshttps://doi.org/10.1145/3313906openalex-snapshot
Tight Lower Bounds for the Complexity of Multicoloring
inferred← citeshttps://doi.org/10.1145/3448639openalex-snapshot
Computation of Hadwiger Number and Related Contraction Problems
inferred← citeshttps://doi.org/10.1145/3652514openalex-snapshot
The Fine-Grained Complexity of Graph Homomorphism Parameterized by Clique-Width
inferred← citeshttps://doi.org/10.3390/sym18101604openalex-snapshot
Improved Exact Algorithm for Finding a Maximum Exploratory Equivalent Partition
inferred← citeshttps://doi.org/10.4230/lipics.ipec.2020.3openalex-snapshot
Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2021.56openalex-snapshot
Fine-Grained Complexity of the List Homomorphism Problem: Feedback Vertex Set and Cutwidth
inferred← citeshttps://doi.org/10.70675/2a7d2deaz145ez4ee9z91d4z066559920227openalex-snapshot
Twin-width : lower bounds and approximation algorithms
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.