Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
From MaRDI portal
Cites work
- A faster pseudopolynomial time algorithm for subset sum
- A hierarchy of lower bounds for sublinear additive spanners
- A near-linear pseudopolynomial time algorithm for subset sum
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A partial k-arboretum of graphs with bounded treewidth
- A spectral theory for tensors
- All non-trivial variants of 3-LDT are equivalent
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Bin packing with fixed number of bins revisited
- Clustered Integer 3SUM via Additive Combinatorics
- Color-coding
- Counting Subgraphs via Homomorphisms
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- Exact weight subgraphs and the k-sum conjecture
- Fast algorithms for knapsack via convolution and prediction
- Faster algorithms for finding and counting subgraphs
- Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
- Graph searching and a min-max theorem for tree-width
- Homomorphisms are a good basis for counting small subgraphs
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 7204473 (Why is no real title available?)
- scientific article; zbMATH DE number 7650232 (Why is no real title available?)
- Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
- Introduction to algorithms.
- Losing weight by gaining edges
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Necklaces, Convolutions, and X + Y
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
- On the complexity of k-SAT
- On the complexity of fixed parameter clique and dominating set
- Powers of tensors and fast matrix multiplication
- Rapid Multiplication of Rectangular Matrices
- SETH-based lower bounds for subset sum and bicriteria path
- SOFSEM 2005: Theory and Practice of Computer Science
- Testing subgraphs in large graphs
- The 4/3 additive spanner exponent is tight
- The complexity of tree partitioning
- Tight hardness for shortest cycles and paths in sparse graphs
- Waring rank, parameterized and exact algorithms
This page was built for publication: Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241137)
