Counting Subgraphs via Homomorphisms

DOI10.1007/978-3-642-02927-1_8MaRDI QIDQ5902149zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Omid Amini, Fedor V. Fomin, Saket Saurabh

Publication date 14 July 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02927-1_8

zbMATH Keywords

color coding based algorithmscomputing chromatic polynomialcounting graph homomorphismscounting Hamiltonian cyclescounting perfect matchingscounting subgraphsexact algorithmsparametrized algorithms

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorics in computer science (68R05)

Recommendations

• Counting subgraphs via homomorphisms
• Counting graph homomorphisms
• Counting graph homomorphisms involving complete graphs
• On the number of homogeneous subgraphs of a graph
• Homomorphisms are a good basis for counting small subgraphs
• Counting homomorphisms to sparse graphs
• Counting subgraphs: A new approach to the Caccetta-Häggkvist conjecture
• scientific article; zbMATH DE number 1545676
• Counting homomorphisms via hypergraph-based structural restrictions
• Counting Subgraphs in Degenerate Graphs

Cited in

(20)

• On the problem of finding small subdivision and homomorphism bases for classes of countable graphs
• Handle bases and bounds on the number of subgraphs
• Multiplicities of subgraphs
• Capacitated domination faster than O(2ⁿ)
• Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• scientific article; zbMATH DE number 6691415 (Why is no real title available?)
• An exponential time 2-approximation algorithm for bandwidth
• An exponential time 2-approximation algorithm for bandwidth
• Faster algorithms for finding and counting subgraphs
• On the parameterized complexity of vertex cover and edge cover with connectivity constraints
• Homomorphisms are a good basis for counting small subgraphs
• Counting subgraphs in hyperbolic graphs with symmetry
• Counting perfect matchings as fast as Ryser
• Classes of graphs embeddable in order-dependent surfaces
• Counting subgraphs via homomorphisms
• Parameterized (Modular) Counting and Cayley Graph Expanders
• New plain-exponential time classes for graph homomorphism
• Exact and approximate bandwidth
• Current algorithms for detecting subgraphs of bounded treewidth are probably optimal

This page was built for publication: Counting Subgraphs via Homomorphisms

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