On the public citation graph

On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs

https://doi.org/10.1145/3154856
0 signed · 72 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.1002/net.10046openalex-snapshot
Solving partial constraint satisfaction problems with tree decomposition
inferredcites →https://doi.org/10.1006/inco.1995.1156openalex-snapshot
On the Structure of Parameterized Problems in NP
inferredcites →https://doi.org/10.1007/11602613_77openalex-snapshot
Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs
inferredcites →https://doi.org/10.1007/978-3-319-06686-8_29openalex-snapshot
Space Saving by Dynamic Algebraization
inferredcites →https://doi.org/10.1007/978-3-540-30577-4_1openalex-snapshot
Discovering Treewidth
inferredcites →https://doi.org/10.1007/978-3-642-25870-1_24openalex-snapshot
Planar k-Path in Subexponential Time and Polynomial Space
inferredcites →https://doi.org/10.1007/978-3-642-27875-4openalex-snapshot
Sparsity (Graphs, Structures, and Algorithms)
inferredcites →https://doi.org/10.1007/978-3-642-39206-1_5openalex-snapshot
Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm
inferredcites →https://doi.org/10.1007/978-3-662-47672-7_40openalex-snapshot
Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
inferredcites →https://doi.org/10.1007/bf01205052openalex-snapshot
RL $$ \subseteq $$ SC
inferredcites →https://doi.org/10.1007/s00453-012-9630-xopenalex-snapshot
Fast Polynomial-Space Algorithms Using Inclusion-Exclusion
inferredcites →https://doi.org/10.1007/s00453-014-9944-yopenalex-snapshot
On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness
inferredcites →https://doi.org/10.1016/0012-365x(93)e0216-qopenalex-snapshot
Ordered colourings
inferredcites →https://doi.org/10.1016/0022-0000(80)90036-7openalex-snapshot
Tree-size bounded alternation
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/0196-6774(91)90006-kopenalex-snapshot
Easy problems for tree-decomposable graphs
inferredcites →https://doi.org/10.1016/0304-3975(76)90059-1openalex-snapshot
Some simplified NP-complete graph problems
inferredcites →https://doi.org/10.1016/0304-3975(94)00251-dopenalex-snapshot
The parameterized complexity of sequence alignment and consensus
inferredcites →https://doi.org/10.1016/0890-5401(90)90043-hopenalex-snapshot
The monadic second-order logic of graphs. I. Recognizable sets of finite graphs
inferredcites →https://doi.org/10.1016/j.cosrev.2014.08.001openalex-snapshot
Practical algorithms for MSO model-checking on tree-decomposable graphs
inferredcites →https://doi.org/10.1016/j.dam.2004.01.013openalex-snapshot
Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
inferredcites →https://doi.org/10.1016/j.disopt.2006.05.008openalex-snapshot
Tree decompositions of graphs: Saving memory in dynamic programming
inferredcites →https://doi.org/10.1016/j.disopt.2010.08.003openalex-snapshot
Parameterized complexity and approximability of the Longest Compatible Sequence problem
inferredcites →https://doi.org/10.1016/j.ejc.2005.01.010openalex-snapshot
Tree-depth, subgraph coloring and homomorphism bounds
inferredcites →https://doi.org/10.1016/j.ipl.2009.09.012openalex-snapshot
A note on width-parameterized SAT: An exact machine-model characterization
inferredcites →https://doi.org/10.1016/s0022-0000(03)00074-6openalex-snapshot
On the existence of subexponential parameterized algorithms
inferredcites →https://doi.org/10.1016/s0022-0000(03)00078-3openalex-snapshot
On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
inferredcites →https://doi.org/10.1016/s0022-0000(70)80006-xopenalex-snapshot
Relationships between nondeterministic and deterministic tape complexities
inferredcites →https://doi.org/10.1051/ita:2001119openalex-snapshot
Division in logspace-uniformNC1
inferredcites →https://doi.org/10.1109/bibe.2007.4375584openalex-snapshot
Shortest Path Approaches for the Longest Common Subsequence of a Set of Strings
inferredcites →https://doi.org/10.1109/focs.2010.21openalex-snapshot
Logspace Versions of the Theorems of Bodlaender and Courcelle
inferredcites →https://doi.org/10.1109/focs.2015.14openalex-snapshot
Tight Hardness Results for LCS and Other Sequence Similarity Measures
inferredcites →https://doi.org/10.1109/lics.2012.37openalex-snapshot
Where First-Order and Monadic Second-Order Logic Coincide
inferredcites →https://doi.org/10.1137/0209046openalex-snapshot
Applications of a Planar Separator Theorem
inferredcites →https://doi.org/10.1137/s0097539793283151openalex-snapshot
A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
inferredcites →https://doi.org/10.1137/s0097539795295948openalex-snapshot
Tight Lower Bounds for st -Connectivity on the NNJAG Model
inferredcites →https://doi.org/10.1137/s0895480195282550openalex-snapshot
Rankings of Graphs
inferredcites →https://doi.org/10.1145/1101821.1101823openalex-snapshot
Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
inferredcites →https://doi.org/10.1145/174644.174650openalex-snapshot
Approximation algorithms for NP-complete problems on planar graphs
inferredcites →https://doi.org/10.1145/1806689.1806735openalex-snapshot
Saving space by algebraization
inferredcites →https://doi.org/10.1145/2603088.2603107openalex-snapshot
One hierarchy spawns another
inferredcites →https://doi.org/10.1145/382780.382783openalex-snapshot
The complexity of acyclic conjunctive queries
inferredcites →https://doi.org/10.1215/ijm/1255631807openalex-snapshot
Approximate formulas for some functions of prime numbers
inferredcites →https://doi.org/10.2168/lmcs-1(1:2)2005openalex-snapshot
Model-Checking Problems as a Basis for Parameterized Intractability
inferredcites →https://doi.org/10.4086/toc.2014.v010a012openalex-snapshot
inferredcites →https://doi.org/10.5287/ora-r88ygpzdxopenalex-snapshot
Exploiting parallelism in decomposition methods for constraint satisfaction

What points at this work

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

inferred← citeshttps://doi.org/10.2139/ssrn.4673490openalex-extracted
Parameterized Problems Complete for Nondeterministic Fpt Time and Logarithmic Space
inferred← citeshttps://doi.org/10.1007/978-3-030-19955-5_4openalex-snapshot
A Space-Efficient Parameterized Algorithm for the Hamiltonian Cycle Problem by Dynamic Algebraization
inferred← citeshttps://doi.org/10.1007/978-3-030-60440-0_3openalex-snapshot
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
inferred← citeshttps://doi.org/10.1007/978-3-030-96731-4_2openalex-snapshot
From the W-hierarchy to XNLP
inferred← citeshttps://doi.org/10.1007/978-3-031-52113-3_12openalex-snapshot
On the Parameterized Complexity of the Perfect Phylogeny Problem
inferred← citeshttps://doi.org/10.1007/978-3-031-75409-8_8openalex-snapshot
XNLP-Hardness of Parameterized Problems on Planar Graphs
inferred← citeshttps://doi.org/10.1007/978-3-032-11835-6_21openalex-snapshot
A Parameterized Complexity Analysis of Bounded Height Depth-First Search Trees
inferred← citeshttps://doi.org/10.1007/978-3-032-11835-6_8openalex-snapshot
Concurrency Constrained Scheduling with Tree-Like Constraints
inferred← citeshttps://doi.org/10.1007/978-3-032-27732-9_11openalex-snapshot
The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
inferred← citeshttps://doi.org/10.1007/s00453-024-01274-9openalex-snapshot
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
inferred← citeshttps://doi.org/10.1007/s00493-025-00168-wopenalex-snapshot
The Grid-Minor Theorem Revisited
inferred← citeshttps://doi.org/10.1016/j.ic.2024.105195openalex-snapshot
Parameterized problems complete for nondeterministic FPT time and logarithmic space
inferred← citeshttps://doi.org/10.1016/j.jctb.2021.06.002openalex-snapshot
Polynomial bounds for centered colorings on proper minor-closed graph classes
inferred← citeshttps://doi.org/10.1016/j.jctb.2025.07.006openalex-snapshot
Closure property of contraction-depth of matroids
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.07.009openalex-snapshot
Polynomial kernels for hitting forbidden minors under structural parameterizations
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00027openalex-snapshot
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
inferred← citeshttps://doi.org/10.1137/1.9781611975482.91openalex-snapshot
Polynomial bounds for centered colorings on proper minor-closed graph classes
inferred← citeshttps://doi.org/10.1137/1.9781611975994.136openalex-snapshot
Improved bounds for centered colorings
inferred← citeshttps://doi.org/10.1137/22m1518943openalex-snapshot
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
inferred← citeshttps://doi.org/10.1145/3406325.3451068openalex-snapshot
Vertex deletion parameterized by elimination distance and even less
inferred← citeshttps://doi.org/10.1145/3723880openalex-snapshot
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
inferred← citeshttps://doi.org/10.19086/aic.27351openalex-snapshot
Improved Bounds for Centered Colorings
inferred← citeshttps://doi.org/10.3390/a11070098openalex-snapshot
Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2020.16openalex-snapshot
Bridge-Depth Characterizes Which Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2021.87openalex-snapshot
Lower Bounds on Dynamic Programming for Maximum Weight Independent Set
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2020.29openalex-snapshot
Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space
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.