Beating treewidth for average-case subgraph isomorphism
From MaRDI portal
Publication:2041983
Recommendations
- scientific article; zbMATH DE number 7650232
- On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
- Faster algorithms for finding and counting subgraphs
- Lower bounds for subgraph isomorphism
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
- A partial k-arboretum of graphs with bounded treewidth
- Can you beat treewidth?
- Color-coding
- Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
- Expander graphs and their applications
- Graph minors. II. Algorithmic aspects of tree-width
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 1179106 (Why is no real title available?)
- scientific article; zbMATH DE number 2060183 (Why is no real title available?)
- scientific article; zbMATH DE number 5485586 (Why is no real title available?)
- Lower bounds for subgraph isomorphism
- On an isoperimetric problem for Hamming graphs
- On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
- On the complexity of fixed parameter clique and dominating set
- Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
- Parameters tied to treewidth
- Poisson approximation for large deviations
- Sparse balanced partitions and the complexity of subgraph problems
- The monotone complexity of \(k\)-clique on random graphs
- The treewidth and pathwidth of hypercubes
- Which problems have strongly exponential complexity?
Cited in
(4)
This page was built for publication: Beating treewidth for average-case subgraph isomorphism
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2041983)
