Detecting and Counting Small Pattern Graphs

DOI10.1137/140978211zbMath1327.68332OpenAlexW2114047496MaRDI QIDQ5502097

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

Publication date: 17 August 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/140978211

zbMATH Keywords

randomized algorithmsexact algorithmsrectangular matrix multiplicationcounting and detection of subgraphssubgraph and induced subgraph isomorphismpolynomial testing

Mathematics Subject Classification ID

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

Related Items

Monotone arithmetic complexity of graph homomorphism polynomials ⋮ 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 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding and counting small induced subgraphs efficiently
• Faster algorithms for finding and counting subgraphs
• On the complexity of fixed parameter clique and dominating set
• Paw-free graphs
• A probabilistic remark on algebraic program testing
• Finding and listing induced paths and cycles
• Counting and Detecting Small Subgraphs via Equations
• Induced Subgraph Isomorphism: Are Some Patterns Substantially Easier Than Others?
• Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
• Limits and Applications of Group Algebras for Parameterized Problems
• A Linear Recognition Algorithm for Cographs
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Finding, minimizing, and counting weighted subgraphs
• Finding Four-Node Subgraphs in Triangle Time
• Multiplying matrices faster than coppersmith-winograd
• Determinant Sums for Undirected Hamiltonicity
• Systems of distinct representatives and linear algebra
• Experimental and Efficient Algorithms