Detecting and Counting Small Pattern Graphs

DOI10.1007/978-3-642-45030-3_51MaRDI QIDQ2872118zbMATH OpenOpenAlexFDO

Authors Peter Floderus, Mirosław Kowaluk, Eva-Marta Lundell, Andrzej Lingas

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_51

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Detecting and counting small pattern graphs
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Detecting and counting small patterns in planar graphs in subexponential parameterized time
• Counting and detecting small subgraphs via equations
• Counting and detecting small subgraphs via equations and matrix multiplication
• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• Finding patterns in an unknown graph
• The total detection numbers of graphs

Cited in

(17)

• Efficient algorithms for subgraph listing
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• Detecting and counting small pattern graphs
• Faster algorithms for finding and counting subgraphs
• Engineering a delegatable and error-tolerant algorithm for counting small subgraphs
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Counting connected subgraphs with maximum-degree-aware sieving
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Rare siblings speed-up deterministic detection and counting of small pattern graphs
• Counting and detecting small subgraphs via equations and matrix multiplication
• A fast deterministic detection of small pattern graphs in graphs without large cliques
• On linear algebraic algorithms for the subgraph matching problem and its variants
• Faster algorithms for counting subgraphs in sparse graphs
• Recognizing small subgraphs
• Counting and detecting small subgraphs via equations
• Finding patterns in an unknown graph

This page was built for publication: Detecting and Counting Small Pattern Graphs

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