Counting and Detecting Small Subgraphs via Equations

DOI10.1137/110859798zbMath1275.68161OpenAlexW2070188445MaRDI QIDQ2848542

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

Publication date: 26 September 2013

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

Full work available at URL: https://semanticscholar.org/paper/e01a8c81787a118eb532963215394a721dd1c78d

zbMATH Keywords

linear equationsexact algorithmsrectangular matrix multiplicationcounting and detection of subgraphssubgraph and induced subgraph isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Counting Subgraphs in Degenerate Graphs ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Unnamed Item ⋮ 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 ⋮ Finding and counting small tournaments in large tournaments ⋮ Detecting and Counting Small Pattern Graphs ⋮ Rare siblings speed-up deterministic detection and counting of small pattern graphs ⋮ Counting Answers to Existential Questions ⋮ Unique subgraphs are not easier to find ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles

This page was built for publication: Counting and Detecting Small Subgraphs via Equations