Counting Subgraphs via Homomorphisms

DOI10.1137/100789403zbMath1248.05122DBLPjournals/siamdm/AminiFS12OpenAlexW2026416569WikidataQ60488474 ScholiaQ60488474MaRDI QIDQ5891745

Omid Amini, Saket Saurabh, Fedor V. Fomin

Publication date: 12 September 2012

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

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

zbMATH Keywords

graph homomorphismsvertex disjoint subgraphs

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (9)

A general purpose algorithm for counting simple cycles and simple paths of any length ⋮ Parameterized complexity of connected even/odd subgraph problems ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Inclusion/exclusion meets measure and conquer ⋮ Unnamed Item ⋮ Stable matching games: manipulation via subgraph isomorphism ⋮ On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models

This page was built for publication: Counting Subgraphs via Homomorphisms