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

(9)

• Detecting and Counting Small Pattern Graphs
• Enumerating grid layouts of graphs
• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• Algorithms and Turing kernels for detecting and counting small patterns in unit disk graphs
• Subexponential parameterized directed Steiner network problems on planar graphs: a complete classification
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• True contraction decomposition and almost ETH-tight bipartization for unit-disk graphs
• Multicut problems in embedded graphs: the dependency of complexity on the demand pattern
• Robust contraction decomposition for minor-free graphs and its applications

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)