scientific article; zbMATH DE number 7650232

DOI10.4230/LIPICS.IPEC.2019.24MaRDI QIDQ5875558zbMATH OpenFDO

Authors Gregory Rosenthal

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2019.24

zbMATH Keywords

AC\(^0\)average-case complexitycircuit complexitysubgraph isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Recommendations

• Beating treewidth for average-case subgraph isomorphism
• 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)

Cited in

(5)

• Beating treewidth for average-case subgraph isomorphism
• Lower bounds for subgraph isomorphism
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• Tree-Depth and the Formula Complexity of Subgraph Isomorphism
• Current algorithms for detecting subgraphs of bounded treewidth are probably optimal

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875558)