Detecting and counting small patterns in planar graphs in subexponential parameterized time

DOI10.1145/3357713.3384261MaRDI QIDQ5145013zbMATH OpenOpenAlexFDO

Authors Jesper Nederlof

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.11285

zbMATH Keywords

parameterized complexitysubgraph isomorphism

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Planar subgraph isomorphism revisited
• Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Detecting and counting small pattern graphs
• Detecting and Counting Small Pattern Graphs

Cited in

(4)

• Detecting and Counting Small Pattern Graphs
• Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs
• Enumerating grid layouts of graphs
• Rare siblings speed-up deterministic detection and counting of small pattern graphs

This page was built for publication: Detecting and counting small patterns in planar graphs in subexponential parameterized time

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